MSET - Make Sets

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

Added by:Sanket Singhal
Date:2015-02-16
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Own Problem(CQM-5 BIT Mesra)

hide comments
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.