Cricket in US

All submissions for this problem are available.
Cricket has caught up in the US as well! There are two teams playing a match. Each team consists of N players. It is a M over match. In each over, one player takes the striker's end and the other player remains in the non striker's end till the end of the over. The two team each have a coach. The second coach is not very good with the rules and sometimes he just sends a single player to play an over without anyone in the non striker's end. But the first coach knows the rules well. In each team, a player will be at the strikers end in at most one over and at the non striker's end in at most one over.
Now the coaches have analysed previous matches and have based their teams's strategy on it. The first teams's coach decides that he will never allow a situation where a Kcycle occurs. A Kcycle happens when a player A_{1} plays some over with player A_{2} at the non strikers end; player A_{2} plays some over where player A_{3} is in the non strikers end,.... player A_{i} plays an over where player A_{i+1} is in the non strikers end and when player A_{k} plays some over where player A_{1} is in the non strikers end. The second coach also decides on a similar strategy. If in an over only one player is sent, then we can consider that the same player is at the non strikers end as well for checking whether there is a Kcycle. He also decides to avoid a Kcycle with this modified definition.
Print the number of ways in the which the first coach can make his team play the M overs, so that his strategy is followed. Similarly print the number of ways in which the second coach can make his team play the M overs, so that his strategy his followed. Print both the numbers modulo 10^{9}+7.
Input
First line contains an integer T which represents the number of test cases.
Each of the next T lines contains 3 space separated integers, N, M, K.
Output
For each test case print two integers which are asked above.
Constraints
 1 ≤ T ≤ 10^{2}
 1 ≤ N ≤ 10^{5}
 1 ≤ M ≤ 10^{12}
 1 ≤ K ≤ N
 Sum of N over all the cases will be ≤ 10^{6}
Example
Input: 1 10 10 10 Output: 487508111 370413043
Author:  ajkrish95 
Tags  ajkrish95 
Date Added:  4072015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 