A website provides its users with a variety of services. There are a total of K services available on that website. At present there are M users/clients registered to the website.

Now each client of this service provider firm is to be allocated a project by the website which makes use of a string A1,A2,A3.............An of N services all of which the website is providing. The order in which the services are executed matters (compiling and then linking is different from linking and then compiling). Also, in a particular project, the same services cannot be executed twice in succession. For example, compiling → linking → compiling is allowed, but linking → linking → compiling is not allowed because 'linking' comes twice in succession.

All the M clients will start working at the same time and the time taken for the execution of all services is equal. At a time, one service can be accessed by only one client as there is only one server. For eg. If there are 3 clients with projects – A1,A2...An ; B1,B2....Bn and C1,C2....Cn , then Ai, Bi, Ci are pairwise distinct for 1 <= i <= N. You need to find in how many ways in which the M clients can be allocated their projects.

Input

First line containing T (number of test cases).

For each test case one line containing 3 integers N ,M and K.

Output

For each test case output a separate line containing the answer modulo 1000000007.

Constraints               

1 <= T <= 10

0 <= N <= 1000000000

1 <= M <= 100

0 <= K <= 1000

Sample Input

3

2 2 3

1 2 3

2 3 4

Sample Output

18

6

264