Bob Likes Invariance

Practice

4.6 (8 votes)

Combinatorics

Basics of combinatorics

C++

Math

Problem

77% Success 809 Attempts 50 Points 1s Time Limit 256MB Memory 1024 KB Max Code

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\)

Sample Input

Sample Output

3
1
11

Explanation

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\).

Code Editor

You need to be logged in to access the code editor

Please wait while we load the editor

Submissions

Please login to view your submissions

You need to be logged in to access the code editor

Please wait while we load the editor