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

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 $x_1$ days and after that, *Inosukeβs* for $y_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** $x_1$

`Γ The number of techniques Zenitsu showed and`

`Γ 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 $T_{i}$, $Z_{i}$ and $I_{i}$ respectively. So,

$T_{i}$ = $T_{i-1}$ + ( $Z_{i-1}$ Γ $x_1$ ) + ( $I_{i-1}$ Γ $y_1$ )

$Z_{i}$ = $Z_{i-1}$ + ( $T_{i-1}$ Γ $x_2$ ) + ( $I_{i-1}$ Γ $y_2$ )

$I_{i}$ = $I_{i-1}$ + ( $T_{i-1}$ Γ $x_3$ ) + ( $Z_{i-1}$ Γ $y_3$ )

Today is such a day! They are going to meet again and **Oyakata-Sama****told me that they have met** $N$ **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

The first line will be a single integer $T$ indicating the number of test cases. The following $T$ lines will contain seven integers $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, $y_3$, $N$ separated by spaces.

*Constraints:*

$1 β€ T β€ 10^{3}$

$0 β€ x_1, y_1, x_2, y_2, x_3, y_3 β€ 10^{9}$

$1 β€ N β€ 10^{9}$

You have to output $T$ lines in format β$Case X: Y$β(without quotes) where $X$ is the number of test case and $Y$ is $T_n\%1000000007$.

Input | Output |
---|---|

3 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. |