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 patten 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 (posibly 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

hide comments
morass: 2017-02-12 02:19:08

[Rampage] Blue.Mary: Sure! Thanks for advice + thanks for piloting tests!!!

[Rampage] Blue.Mary: 2017-02-12 02:15:08

This should be put into tutorial section because large numbers of (direct) Matrix multiplication problem exists in SPOJ classical section.


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