#1607 SuperSum

1 s   128 MB  

Description

SuperSum is a function defined as:

  • SuperSum(0 , n) = n, for all positive n.
  • SuperSum(k , n) = SuperSum(k-1 , 1) + SuperSum(k-1 , 2) + ... + SuperSum(k-1 , n), for all positive k, n.

Given k and n, print the value for SuperSum(k , n) modulo 1000000007.

Input

The first line of the input gives the number of test cases, T (1 <= T <= 500).

For each test case, two integers k and n will be given in one line. n will be between 1 and 1,000,000,000, inclusive. k will be between 1 and 100, inclusive.

Output

For each test case, print SuperSum(k, n), in one line.

Sample Input

Sample Output

4
1 3
2 3
4 10
10 35
6
10
2002
150595840