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

Output
18
6
264