WPC5D - Complicated Calculations
There are k galaxies that participate in the Galactical Wars, which have happened for the past n years. Each year there has been a victor. Further, a particular galaxy G has won the Wars an even number of times. Also, G didn't participate in the first year.
You are a member of the old and wise community of Daba. Even though it is the festive season of Galaxy going on, you prefer to sit in your room and do complicated (and senseless) calculations. For no reason, one day, you wonder in how many possible ways the victories in the previous years could have taken place (that is, the number of different sequences of victors possible). Output the result of this complicated (and senseless) calculation.
Input
First line contains a single integer T, denoting the number of Test Cases.
T lines follow, containing space separated integers: n and k, as described in the problem.
Output
T lines, each containing the number of ways in which victories during n years could have taken place, modulo 1000000007 (10^9 + 7).
Constraints
1 <= T <= 150,000
1 <= n, k <= 10^9
Example
Input: 1 1 4 Output: 3
Explanation
Any Galaxy except āGā could have won. There are 3 such galaxies.
hide comments
Chetan:
2014-09-28 09:56:31
Took me a while to detect where I was going wrong!
|
|
Bhavik:
2014-06-12 18:24:14
here's one:
|
|
Atul Aditya:
2014-06-12 17:24:21
some more test cases plzz :(
|
|
XYZ:
2014-06-12 07:25:35
How about giving one more test case? |
Added by: | triveni |
Date: | 2014-03-29 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | ACA judge IITK, WPC5 |