Help Sherlock

All submissions for this problem are available.
Sherlock has fallen in love with Irene Addler(The Woman), now he wants to impress her. Irene wants to see how clever he actually is. She asks Moriarty to give her some problem. Moriarty designs the problems as follows:
Given two number N and M as input find numbers such as:
1. The number should contain all the digits from 0 to N1
2. The length of number can be atmost M i.e. it can have atmost M digits.
3. The difference between each adjacent digits should be one.
calculate the number of all such numbers.
Sherlock had no idea to solve this problem help him and prove you are better than him!!
For e.g.
1. if N=7 and M=8, you are supposed to use all the 0 to 6 digits and the length of the number can be atmost 8 digits. So, possible solutions are 6543210, 65432101, 56543210, 10123456. So, ans is 4.
Note: The numbers starting with 0 will be treated as if 0 have been removed from starting, for the above solution 0123456 will be considered as 123456(the length is 6 not 7) only and as 0 is not appearing in the number, it is not a valid solution
Input
First line T : no. of test cases
For each test case: N M (space separated)
Output
For each test case no. of such numbers that can be formed using all 0(N1) digits and which have atmost M digits in single line.
Output should be in Modulo 1000000007
Constraints
Example
Input: 4 2 4 5 5 3 6 7 14 Output: 3 1 18 1639
Explaination
Test case 1:
N=2 means 0 and 1 both has to be used only and M = 4 means at most 4 times these digits can be used. So, possible solutions are 10,101,1010 (3) //01 is not such a number
Test Case 2:
N=5 (04), M=5 43210 is only possible solution by using all the digit.
Author:  harshg0910 
Tags  harshg0910 
Date Added:  14082013 
Time Limit:  0.12 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, 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