Here Is a Treat for You πŸ•πŸ”

Limits 1s, 512 MB

Kagaya Ubuyashiki, the 97-th leader of the Demon Slayer Corps, Also known as Oyakata-sama to the Demon Slayer Corps, just met Tanjiro, Zenitsu, and Inosuke. Instantly, he knew there is something special about them. But as special they are, they also need special training to make their ability grow faster as well. You know they can be trained best by the hashiras(highest rank of demon slayers) but the hashiras are busy slaying demons (Don’t worry they respect the pandemic they are wearing masks, and saving people from demons is more important to them than quarantining right now). They are spread all around the world. They can’t come to the demon slayer headquarters to teach them. So, the Oyakata-Sama made a scheme so that they can learn properly.

Initially, Tanjiro, Zenitsu, and Inosuke each knew only one breathing technique. Then all three meet at the demon slayer headquarters every time they get free to teach their breathing techniques to each other. After that, they go separate ways and practice those breathing techniques under different hashiras. Tanjiro practices the techniques shown by Zenitsu for x1x_1 days and after that, Inosuke’s for y1y_1 days. But, as Tanjiro goes to train under the hashiras, they influence those techniques in a way that the number of breathing techniques Tanjiro knows increases by the summation of x1x_1 Γ— The number of techniques Zenitsu showed and y1y_1 Γ— The number of techniques Inosuke showed. In the same way, Zenitsu’s and Inosuke’s practices get influenced following the rule mentioned below-

Lets say, after i-th meeting and finishing practice the number of breathing techniques Tanjiro, Zanitsu and Inosuke know are TiT_{i}, ZiZ_{i} and IiI_{i} respectively. So,

TiT_{i} = Tiβˆ’1T_{i-1} + ( Ziβˆ’1Z_{i-1} Γ— x1x_1 ) + ( Iiβˆ’1I_{i-1} Γ— y1y_1 )

ZiZ_{i} = Ziβˆ’1Z_{i-1} + ( Tiβˆ’1T_{i-1} Γ— x2x_2 ) + ( Iiβˆ’1I_{i-1} Γ— y2y_2 )

IiI_{i} = Iiβˆ’1I_{i-1} + ( Tiβˆ’1T_{i-1} Γ— x3x_3 ) + ( Ziβˆ’1Z_{i-1} Γ— y3y_3 )

Today is such a day! They are going to meet again and Oyakata-Sama told me that they have met NN times before today. So, I was wondering how many techniques Tanjiro know before the meeting (Why Tanjiro? I’ll leave it to your imagination πŸ˜‰). Anyway, the number of techniques Tanjiro know at this point might be so big that it might not fit into a 32-bit integer ( this is Demon Slayer in some parallel universe anything is possible πŸ˜‰) that is why you have to output the value modulo 109+7(1000000007)10^{9}+7(1000000007). In other words, Print Tn%1000000007T_n\%1000000007, initially T0=1,Z0=1,I0=1T_0=1, Z_0=1, I_0=1.


The first line will be a single integer TT indicating the number of test cases. The following TT lines will contain seven integers x1x_1, y1y_1, x2x_2, y2y_2, x3x_3, y3y_3, NN separated by spaces.


1≀T≀1031 ≀ T ≀ 10^{3}

0≀x1,y1,x2,y2,x3,y3≀1090 ≀ x_1, y_1, x_2, y_2, x_3, y_3 ≀ 10^{9}

1≀N≀1091 ≀ N ≀ 10^{9}


You have to output TT lines in format β€œCaseX:YCase X: Y”(without quotes) where XX is the number of test case and YY is Tn%1000000007T_n\%1000000007.


1 2 0 0 0 0 3
1 1 1 1 1 1 4
1 0 1 0 1 0 10
Case 1: 10
Case 2: 81
Case 3: 1024

For the 1st test case Initially, Tanjiro knows 1 technique, Zenitsu knows, 1 technique Inosuke knows 1 technique

After 1st meeting and finishing their practice,

Tanjiro knows 1+1Γ—1+2Γ—1=4 techniques Zenitsu knows 1+0Γ—1+0Γ—1=1 technique Inosuke knows 1+0Γ—1+0Γ—1=1 technique

After 2nd meeting and finishing their practice,

Tanjiro knows 4+1Γ—1+2Γ—1=7 techniques Zenitsu knows 1+0Γ—1+0Γ—1=1 technique Inosuke knows 1+0Γ—1+0Γ—1=1 technique

After 3rd meeting and finishing their practice, Tanjiro, Zenitsu and Inosuke know 10 techniques, 1 technique and 1 technique respectively.