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: (((MmodV[0])modV[1])...modV[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 109+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 109+7.
Constraints
1≤T≤101≤N,Z≤105
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 (((MmodV[0])modV[1])...modV[N−1]) with M=13, for various shufflings of the array [1,2,3]:
- [2,1,3]→(((13mod2)mod1)mod3)=((1mod1)mod3)=(0mod3)=0
- [3,2,1]→(((13mod3)mod2)mod1)=((1mod2)mod1)=(1mod1)=0
- [1,2,3]→(((13mod1)mod2)mod3)=((0mod2)mod3)=(0mod3)=0
Similarly, the other shufflings of [1,2,3] will give the result 0 forM=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.
