Given integers N and M, output in how many ways you can take N distinct positive integers such that sum of those integers is ≤ M. Since the result can be huge, output it modulo 1000000007 (10⁹ + 7)

N ≤ 20 

M ≤ 100000

Input

First line of input is number t, number of test cases. Each test case consists only of 2 numbers N and M, in that order.

Output

Output the answer asked for in the description.

Example

Input:
4
6 16
4 16
1 14
3 7
Output:
0
27
14
2