ADAMONEY - Ada and Economy

Ada the Ladybug thinks she found out the key of her economy business. Ada is a farmer and she thinks she found a pattern in the way she makes money. She sees that the money for the next day can be counted from past days as the money she had during previous day plus double the money she had two days before plus five times the money she had four days before plus the money she had five days before. Simple isn't it? Well she wants this system to be automatic, so she had asked you to make a program for it.

Oh, one more thing. You must take one mind, that she buys a tractor as soon as she have enough money for it (possibly multiple tractors if it is possible). The cost of tractor is 109+7

Input

The first line contains 1 ≤ T ≤ 1000, the number of test-cases.

Each of the following T lines contains 6 integers 0 ≤ T0,T1,T2,T3,T4 < 109+7, meaning the money she has in the first 5 days, and 0 ≤ N ≤ 1016 meaning the Nth day for which she wants to know the money she will posses.

As you hopefully understood, today is day 0

Output

For each test-case print the amount of money she will have in Nth day (the money is counted at the end of a day, after she buys all tractors!).

Example Input

7
1 1 1 1 1 5
1 2 3 4 5 6
4 2 5 6 4 10
1 2 1 2 1 15
1 2 1 1 2 20
1 0 0 0 0 19
2 4 8 16 32 1024

Example Output

9
51
1777
49552
3128538
62128
565476237

Added by:Morass
Date:2017-02-11
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2022-09-28 07:24:09
First we have to do the task of the best cases, that is the value of the n is less than 5. On that case our answer will be come directly from the T array. So we have to count from the 5th index. First try to find the genaral equation. That is the for every value of the pemutated array T. The eqution will be the

A(i) = A(i - 1) + 2 * A(i - 2) + 5 * A(i - 4) + A(i - 5)

So, first try to build the matrixes,

T = | 0 1 2 3 4 5
--|----------------------------------------------------------------
0 | 0 0 0 0 0 0
--|----------------------------------------------------------------
1 | 0 1 2 0 5 1 -> this will carry out the relation of the equation
--|---------------------------------------------------------------
2 | 0 1 0 0 0 0
--|----------------------------------------------------------------
3 | 0 0 1 0 0 0
--|----------------------------------------------------------------
4 | 0 0 0 1 0 0
--|---------------------------------------------------------------
5 | 0 0 0 0 1 0
--|---------------------------------------------------------------

So our final mat will be the T^(n - 4).

and the total number will come from the 1'th index of the matrix

ans = sum(T(1, i) * T(j)), 1 <= i <= 5, 4 >= j >= 1



Last edit: 2022-09-28 07:40:13
2022-06-16 23:44:43 David
Beware. N can be 4 or less!
2020-12-25 20:34:16
basic matrix expo
2017-02-12 02:19:08
[Rampage] Blue.Mary: Sure! Thanks for advice + thanks for piloting tests!!!
2017-02-12 02:15:08 [Rampage] Blue.Mary
This should be put into tutorial section because large numbers of (direct) Matrix multiplication problem exists in SPOJ classical section.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.