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 K-cycle occurs. A K-cycle happens when a player A1 plays some over with player A2 at the non strikers end; player A2 plays some over where player A3 is in the non strikers end,.... player Ai plays an over where player Ai+1 is in the non strikers end and when player Ak plays some over where player A1 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 K-cycle. He also decides to avoid a K-cycle 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 109+7.
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.
For each test case print two integers which are asked above.
- 1 ≤ T ≤ 102
- 1 ≤ N ≤ 105
- 1 ≤ M ≤ 1012
- 1 ≤ K ≤ N
- Sum of N over all the cases will be ≤ 106
Input: 1 10 10 10 Output: 487508111 370413043
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.