Machine Mayhem

All submissions for this problem are available.
It's the year 4224 and Giant Machine Corporation has started working on it’s
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 i^{th} step, one of the N parts is chosen and added
to the current robot. After the M^{th} step, the robot is ready.
Let num(i, j) be the count of part number j till the i^{th} 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 10^9 + 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 Format:
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 Format:
For each test case, print in a single line the required number.
Constraints:
1 ≤ T ≤ 20
1 ≤ N ≤ 50
1 ≤ M ≤ 10^18
Sample Input:
3 1 1 2 2 3 2
Sample Output:
1 4 6
Problem Setter: Vivek Hamirwasia
Author:  darkshadows 
Tags  darkshadows 
Date Added:  28012014 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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, 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. 