Math Homework

Time Limit: 3000 Ms

Memory Limit: 65535 Kb

Description

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,youshould only work out the ans mod 1000000007).

Input

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

Output

For each case, you should output one line contains an integer, the answer to the problem.

a, b, c, n ≥ 0 and fit in 32-bit signed number

k + k′≤ 10

Sample Input

1
2 0 1 3 1 1

Sample Output

10

Hint

We amuse that 00=1

 

Source

2013 ACM-ICPC China Nanjing Invitational Prog

提交代码