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 3 24 37 10 10 Sample Output 3 31 1