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^9 + 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