#include<bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define memo(a,v) memset(a,v,sizeof(a))
#define pb push_back
#define all(a) a.begin(),a.end()
#define eps (1e-9)
#define inf (1<<29)
#define i64 long long
#define u64 unsigned i64
#define AIN(a,b,c) assert(a<=b && b<=c)
#define MAXN 1000000000
#define MAX 500
#define MOD 1000000007

typedef pair<int,int> pii;

int mat[MAX][MAX],res[MAX][MAX],tmp[MAX][MAX];
void mult(int a[MAX][MAX],int b[MAX][MAX],int c[MAX][MAX],int n){
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            tmp[i][j] = 0;
            for(int k = 0;k<n;k++){
                tmp[i][j] += (a[i][k]*(i64)b[k][j])%MOD;
                tmp[i][j] %= MOD;
            }
        }
    }
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            c[i][j] = tmp[i][j];
        }
    }
}
vector<int> pf, cnt;
int main(){
    int t, n, k, i,m, L, R, d, j, p, c, mask, nmask;
    scanf("%d",&t);
    AIN(1,t,10);
    while(t--){
        scanf("%d %d %d %d",&n,&m,&L,&R);
        AIN(1,n,5000000);
        AIN(1,L,R);
        AIN(L,R,m);
        AIN(R,m,1000);
        int ans = 0;
        for(d = L;d<=R;d++){
            int k = d;
            pf.clear();
            cnt.clear();
            for(i = 2;i*i<=k;i++){
                if(k % i) continue;
                c = 0;
                while(k%i==0){
                    k/=i;
                    c++;
                }
                pf.pb(i);
                cnt.pb(c);
            }
            if(k>1){
                pf.pb(k);
                cnt.pb(1);
            }
            int p = pf.size();
            memset(mat,0,sizeof(mat));
            memset(res,0,sizeof(res));
            for(mask = 0;mask < (1<<p);mask++){
                for(i = 1;i<=m;i++){
                    nmask = mask;
                    for(j = 0;j<p;j++){
                        k = i;
                        c = 0;
                        while(k%pf[j]==0)
                        {
                            k/=pf[j];
                            c++;
                        }
                        if(c>=cnt[j]){
                            nmask |= (1<<j);
                        }
                    }
                    mat[mask][nmask]++;
                }
            }
            k = 1<<(p+1);
            for(i = (1<<p),c = 0;i<k;i++,c++){
                mat[i][c] = 1;
            }
            for(i = 0;i<k;i++){
                res[i][i] = 1;
            }
            for(i = 0;(1<<i)<=n;i++){
                if(n & (1<<i))
                    mult(res,mat,res,k);
                mult(mat,mat,mat,k);
            }
            ans+= res[0][(1<<p)-1];
            ans%=MOD;
        }
        printf("%d\n",ans);
    }
 //   AIN (1, cnt, 500000);
	return 0;
}