Problem B
Beautiful Numbers
Time Limit : 3 seconds
 

 

An N-based number is beautiful if all of the digits from 0 to N-1 are used in that number and the difference between any two adjacent digits is exactly 1 (one). For example, 9876543210 is a 10-based beautiful number. You have to calculate the number beautiful numbers that has got atmost M digits..

Note: No leading zero is allowed in a beautiful number.

 

  
  Input    
  The first line of input is an integer T (T<100) that indicates the number of test cases. Each case starts with a line containing two integers N and M ( 2≤N≤10 & 0≤M≤100 ).  
     
  Output  
  For each case, output the number of beautiful N-based numbers, which are using less than or equal to M digits in a single line. You have to give your output modulo 1000000007.  
     
  Sample Input Sample Output    
  3
2 4
3 7
10 10		 3
31
1		  
 

Problem Setter: Md. Arifuzzaman Arif
Special Thanks: Sohel Hafiz
Next Generation Contest 5