PSERVICE - Permutations

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

Added by:Surya Kiran
Date:2013-09-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Codeblitz-4

hide comments
2013-09-05 20:48:39 Surya kiran
I think "Now each client of this service provider firm is to be allocated a project" should make it clear that the Ai is chosen by the website but not by the client.
2013-09-05 20:48:39 Mitch Schwartz
For me the problem is unclear. I suppose the N services for each client aren't fixed (as we aren't given them as part of the input), and the intended interpretation is: How many ways are there to construct an MxN matrix A such that for all valid i,j,k, (1) A_{i,j} is in {1, 2, ... , K}, (2) A_{i,j} != A_{i,j+1}, (3) if i!=k then A_{i,j} != A_{k,j}. And in particular if M>K (and N>0) then I guess the answer is zero (if we try to understand it as a real-world problem, it simply means that some clients will need to wait some of the time, but for here I don't see any obvious way to fit it into a meaningful counting problem). This interpretation fits with the sample input/output, but I think a sentence like "The Ai are chosen by the website, not the client, and each Ai can be any of the K available services, provided that certain restrictions are met" after the first sentence of the second paragraph would make it much clearer. And I don't think "Ai != Bi != Ci" is a standard way to specify that Ai,Bi,Ci are (pairwise) distinct.

Edit: Got AC according to above interpretation.

Edit 2: Thanks for the reply and for making some changes to the problem statement. Maybe I have a bias toward the idea that clients generally tell servers what they want, and not the other way around, so it took some re-reading to get to the correct interpretation initially. Anyway, it was a fun problem, thanks.

Last edit: 2013-09-06 10:35:34
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.