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 10^{9}+7
Input
The first line contains 1 ≤ T ≤ 1000, the number of testcases.
Each of the following T lines contains 6 integers 0 ≤ T_{0},T_{1},T_{2},T_{3},T_{4} < 10^{9}+7, meaning the money she has in the first 5 days, and 0 ≤ N ≤ 10^{16} meaning the N^{th} day for which she wants to know the money she will posses.
As you hopefully understood, today is day 0
Output
For each testcase print the amount of money she will have in N^{th} 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:
20170212 02:19:08
[Rampage] Blue.Mary: Sure! Thanks for advice + thanks for piloting tests!!! 

[Rampage] Blue.Mary:
20170212 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:  20170211 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 