Sereja and GCD   Problem code: SEAGCD

 

All submissions for this problem are available.

Read problems statements in and .

In this problem Sereja is interested in the number of arrays of integers, A₁, A₂, ..., A_N, with 1 ≤ A_i ≤ M, such that the greatest common divisor of all of its elements is equal to a given integer D.

Find the sum of answers to this problem with D = L, D = L+1, ..., D = R, modulo 10⁹+7.

Input

The first line of the input contains an integer T - the number of test cases. T tests follow, each containing a single line with the values of N, M, L, R.

Output

For each test case output the required sum, modulo 10⁹+7.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ L ≤ R ≤ M

Subtasks

• Subtask #1: 1 ≤ N, M ≤ 10 (10 points)
• Subtask #2: 1 ≤ N, M ≤ 1000 (30 points)
• Subtask #3: 1 ≤ N, M ≤ 10⁷ (60 points)

Example

Input:25 5 1 55 5 4 5Output:31252

对于一个 d , 1~m中有 m/d个数是 d的倍数， 自然就是有 (m/d)^n种排列方法。

然而 ， 这些排列当中，元素必须包含 d , 只要它减去那些只包含它的倍数的序列即可得出结果。

#include 
      
       #include 
       
        using namespace std ;typedef long long LL;const int mod = 1e9+7;const int N = 10000100;LL A[N] ;LL q_pow( LL a , LL b ) {    LL res = 1 ;    while( b ) {        if( b&1 ) res =  res * a  % mod ;        a = a * a % mod ;        b >>= 1;    }    return res ;}int main() {//    freopen("in.txt","r",stdin);    int _ ; cin >> _ ;    while( _-- ) {        LL n , m , l , r ;        cin >> n >> m >> l >> r ;        for( int d = m ; d >= l ; --d ) {            if( d == m || m/d != m/(d+1) ) A[d] = q_pow( m/d , n );            else A[d] = A[d+1] ;        }        for( int i = m ; i >= l ; --i ) {            for( int j = i + i ; j <= m ; j += i ) {                A[i] =( ( A[i] - A[j] ) % mod + mod ) % mod ;            }        }        LL ans = 0 ;        for( int i = l ; i <= r ; ++i )            ans = ( ans + A[i] ) % mod ;        cout << ans << endl ;    }}