For a given number N you have K copies of each number from 1 to N. Therefore, you have a total of N*K numbers. You need to form M sets s1, s2, s3, .... sm where a set should contain unique numbers (set may be empty).

Now, let D be the sum of size of all M sets. (Where the size of a set is number of elements in it)

Let G(i) = number of ways to form M sets such that D is equal to i.

Find G(0) + G(1) + ... G(N*K) modulo 10^9 + 7.
Note: Ordering of sets matters as the sets are numbered.

For example
N = 2, M = 2, K = 2
So, the numbers present initially are (1, 1, 2, 2)
G(0) = 1,
{ }, { }

G(1) = 4:

• {1}, { }
• {2}, { }
• { }, {1}
• { }, {2}

G(2) = 6:

• {1}, {2}
• {2}, {1}
• {1}, {1}
• {2}, {2}
• {1, 2}, { }
• { }, {1, 2}

G(3) = 4:

• {1, 2}, {1}
• {1, 2}, {2}
• {1}, {1, 2}
• {2}, {1, 2}

G(4) = 1:

• {1, 2}, {1, 2}

Where { } represents empty set. So answer = G(0) + G(1) + G(2) + G(3) + G(4) = 16

Input

First line of input consists of integer t denoting number of test cases. Each of the following t lines contain 3 integers N, M, K where N >= M >= K

Output

Output consists of t lines. Each line contains the answer modulo 10^9 + 7.

Constraints

1 <= t <= 100
1 <= M <= N <= 100000
0 <= K <= M

Example

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

Output:
16
256
8