#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <cstdio>
#include <cstring>
 
using namespace std;
 
const long long md = 1000000007;
long long a[100][100];
long long q[100][100];
long long New[100][100];
int d[100];
int p[1111];
int gcd[1111][1111];
 
int Gcd(int x, int y){
    if (x > 1000){
        x %= y;        
    }
 
    if (x < y) swap(x, y);
    if (y == 0) return x;
    if (gcd[x][y] != 0) return gcd[x][y]; else
        return gcd[x][y] = Gcd(x - y, y);
}
 
int main(){
    //freopen("3.tst", "r", stdin);
    //freopen("3.ans", "w", stdout);
    int T;
    cin >> T;
    while (T){
        T--;
        int n, m, l, r;
        cin >> n >> m >> l >> r;
 
        long long ans = 0;
 
        for (int g = l; g <= r; g++){
            int sz = 0;
            for (int i = 1; i <= m; i++){
                p[i] = 0;
            }
            for (int i = 1; i <= m; i++)
            if (g % i == 0){
                sz++;
                d[sz] = i;
                p[i] = sz;
            }
 
            memset(a, 0, sizeof(a));
 
            for (int i = 1; i <= sz; i++){
                for (int j = 1; j <= m; j++){
                    int G = Gcd(d[i], j);
                    G = j / G * d[i];
                    G = Gcd(G, g);
                    //cout << d[i] << " " << j << " " << G << endl;
                    if (p[G]){
                        a[i][p[G]]++;
                        //cout << i << " " << p[G] << endl;
                    }
                }
            }
 
            memset(q, 0, sizeof(q));
            for (int i = 1; i <= sz; i++){
                q[i][i] = 1;
            }
 
            int nn = n;
 
            while (nn){
                if (nn & 1){
                    for (int ii = 1; ii <= sz; ii++){
                        for (int jj = 1; jj <= sz; jj++){
                            New[ii][jj] = 0;
                            for (int kk = 1; kk <= sz; kk++){
                                New[ii][jj] = (New[ii][jj] + q[ii][kk] * a[kk][jj]) % md;
                            }
                        }
                    }
                    for (int ii = 1; ii <= sz; ii++){
                        for (int jj = 1; jj <= sz; jj++){
                            q[ii][jj] = New[ii][jj];
                        }
                    }
                }
 
                for (int ii = 1; ii <= sz; ii++){
                    for (int jj = 1; jj <= sz; jj++){
                        New[ii][jj] = 0;
                        for (int kk = 1; kk <= sz; kk++){
                            New[ii][jj] = (New[ii][jj] + a[ii][kk] * a[kk][jj]) % md;
                        }
                    }
                }
                for (int ii = 1; ii <= sz; ii++){
                    for (int jj = 1; jj <= sz; jj++){
                        a[ii][jj] = New[ii][jj];
                    }
                }
 
                nn /= 2;
            }
 
            
            ans = (ans + q[1][sz]) % md;            
        }
        cout << ans << endl;
    }
    return 0;
}