MACHMAY - Machine Mayhem

It's the year 4224 and Giant Machine Corporation has started working on its 42nd Generation Robots. These robots are designed to have peculiar specifications.

The company has N different parts (numbered from 1 to N), each of which impart a very specific property to the robot. The formation of a single robot R consists of M steps. At the ith step, one of the N parts is chosen and added to the current robot. After the Mth step, the robot is ready. Let num(i, j) be the count of part number j until the ith step used for making the robot R.

The 41st Generation Robots were found to be defective in the sense that one of their properties overshadowed their other properties significantly. Hence, for the 42nd Generation, it was decided that for any robot R, |num(i, j) – num(i, k)| ≤ 2 for every 1 ≤ i ≤ M and for every pair of j, k where 1 ≤ j, k ≤ N.

Now, the Giant Machine Corporation is interested to know the number of different 42nd Generation Robots that they can make which satisfy the above criteria and hence they have hired you for the task. Since, this number can be very large, output the result modulo 109 + 7.

Note: Two robots R1 and R2 are considered different, if a different part is used in any of the corresponding i steps out of M steps.

Input

The first line starts with an integer T, denoting the number of test cases. T lines follow with each line consisting of two space separated integers M and N.

Output

For each test case, print in a single line the required number.

Constraints

1 ≤ T ≤ 20
1 ≤ N ≤ 50
1 ≤ M ≤ 1018

Example

Input:
3
1 1
2 2
3 2

Output:
1
4
6

Problem Setter: Vivek Hamirwasia.


Added by:darkshadows
Date:2014-01-28
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-02-08 13:06:09 Vivek H.
@Mitch Schwartz : Yes, that is right.
2014-02-08 09:13:01 Mitch Schwartz
To clarify, we can use the same part multiple times in a given robot, and num(i,j) is the number of times we have used part j after step i.

Last edit: 2014-02-08 06:24:18
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.