WPC5D - Complicated Calculations

no tags 

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!
Nice Problem! :)

Few Test Cases:

3
10 5
6 5
4 10

O/P
3945616
6736
6804

Last edit: 2015-01-29 11:09:43
Bhavik: 2014-06-12 18:24:14

here's one:
1
3 3

10

Last edit: 2014-06-12 19:19:04
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