In how many ways can R coins be placed on an N × M grid such that each row and each column have at least 1 coin?

Input

The first line contains the number of test cases T. T lines follow containing 3 integers: N, M and R. (1 ≤ T ≤ 100. 1 ≤ N, M ≤ 200. 1 ≤ R ≤ N × M)

Output

Output T lines, one for each test case, containing the output for the corresponding test case. Output all values modulo 1000000007.

Example

Input:
3
1 1 1
2 1 1
2 3 3

Output:
1
0
6