Alice has a lot of math homework to do today. All the problems have the same form: Please find out:
However Alice is not interested at the homework at all. Can you write a program to help her?(As the answer may be very large,you should only work out the ans mod 1000000007).
输入解释
The first line of the input contains an integer T which means the number of test cases. Then T lines follow, each line consists of six non-negative integers, a; b; c; n; k; k′. a, b, c, n ≥ 0 and fit in 32-bit signed number k + k′≤ 10
输出解释
For each case, you should output one line contains an integer, the answer to the problem.