#11472Beautiful Numbers

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.

3
2 4
3 7
10 10

3
31
1