Your friend Bob loves playing with his arrays. He will keep randomly shuffling any array you give him. Let us say you give him a strictly increasing array \(V\) of length \(N\).
Bob will be happy if he has an array \(V\) such that, regardless of how many times he shuffles it, the following value remains the same: \(( ( ( M \mod V[ 0 ] ) \mod V [ 1 ] ) ... \mod V [ N - 1 ] )\), for every non-negative number \(M\).
Given that the elements of \(V\) can be in the range \([1,Z]\). Find the count of the strictly increasing arrays \(V\) that will make Bob happy, modulo \(10^9 + 7\).
Input Format
- The first line of input contains a single integer \(T\), which denotes the number of test cases.
- The first line of each test case contains two integers, \(N\) and \(Z\), denoting the length of the array \(V\) and the maximum value of its elements, respectively.
Output Format
For each test case, print the count of the strictly increasing arrays \(V\) that will make Bob happy, modulo \(10^9 + 7\).
Constraints
\(1 \leq T \leq 10 \\ 1 \leq N, Z \leq 10^5\)
For test case \(1\):
The possible arrays \(V\) that will make Bob happy are: \([ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ]\). Let us try calculating the value \(( ( ( M \mod V[ 0 ] ) \mod V [ 1 ] ) ...\mod V [ N - 1 ] )\) with \(M = 13\), for various shufflings of the array \([ 1, 2, 3 ]\):
- \([ 2, 1, 3 ] \rightarrow (((13 \mod 2) \mod 1) \mod 3) = ((1 \mod 1) \mod 3) = (0 \mod 3) = 0\)
- \([ 3, 2, 1 ] \rightarrow (((13\mod 3) \mod 2) \mod 1) = ((1 \mod 2) \mod 1) = (1 \mod 1) = 0\)
- \([ 1, 2, 3 ] \rightarrow (((13 \mod 1) \mod 2) \mod 3) = ((0 \mod 2) \mod 3) = (0 \mod 3) = 0\)
Similarly, the other shufflings of \([ 1, 2, 3 ]\) will give the result \(0\) for\(M = 13\). Similar invariance will hold for all values of \(M\) for all three arrays. Therefore, the answer is \(3\).
For test case \(2\):
The only \(V\) that can be made is \([ 1, 2, 3 ]\), which will make Bob happy. Thus the answer is \(1\).
For test case \(3\):
There are \(11\) different \(V\) that make Bob happy. Some of them are: \([ 1, 5, 6 ], [ 1, 3, 4 ], [ 1, 2, 3 ]\). Thus the answer is \(11\).
