Problem Description

As we know, sequence in the form of $a_n=a_1+(n-1)d$ is called arithmetic progression and sequence in the form of $b_n=b_1 q^{n-1}(q>1, b_1≠0)$ is called geometric progression. Huazheng wants to use these two simple sequences to generate a simple matrix. Here is what he decides to do:
Use the geometric progression as the first row of the simple matrix: $c_{0,n}=b_n$
Use the arithmetic progression as the first column of the simple matrix: $c_{n,0}=a_n$
Calculate the item at $n$-th row, $m$-th column of the simple matrix as $c_{n,m}=c_{n-1,m}+c_{n,m-1}$, where $n≥1$ and $m≥1$.
Given the two sequences, Huazheng wants to know the value of $c_{n,m}$, but he is too busy with his research to figure it out. Please help him to work it out. By the way, you can assume that $c_{0,0}=0$.

Input

The first line of input contains a number $T$ indicating the number of test cases ($T≤200$).
For each test case, there is only one line containing six non-negative integers $b_1,q,a_1,d,n,m$. ($0≤n≤10000$). All integers are less than $2^{31}$.

Output

For each test case, output a single line consisting of “Case #X: Y”. $X$ is the test case number starting from 1. $Y$ is $c_{n,m}$ module 1000000007.

2
3 10 1 1 3 3
5 2 1 10 4 2

Case #1: 423
Case #2: 140