

Simple MatrixTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 662 Accepted Submission(s): 222 Problem Description As we know, sequence in the form of $a_n=a_1+(n1)d$ is called arithmetic progression and sequence in the form of $b_n=b_1 q^{n1}(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_{n1,m}+c_{n,m1}$, 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 nonnegative 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. Sample Input
Sample Output
Source  
