#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 100005
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
ll k, b, d, l, r;
ll dp[65][65][2][2]; //前i位，有j位是d，当前位是否有最高位限制，是否有前导0 的方案数
ll digit[65];

ll qpow(ll a,ll b){
    if(a==0)
        return 0;//0^0=0
    ll ans = 1;
    b %= mod;
    while(b){
        if(b&1)
            ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}

ll dfs(int pos,int cnt,int lim,int lead){
    if(!pos)
        return qpow(cnt, k);
    if(dp[pos][cnt][lim][lead] != -1){
        return dp[pos][cnt][lim][lead];
    }
    int up = lim ? digit[pos] : (b - 1);
    ll res = 0;
    if(d==up){
        res += dfs(pos - 1, cnt + 1, lim, 0); //填d
        if(lead){
            res += dfs(pos - 1, cnt, 0, 1);    //填0
            res += (up - 1) * dfs(pos - 1, cnt, 0, 0) % mod;  //不填up和0
        }
        else
            res += up * dfs(pos - 1, cnt, 0, 0) % mod; //不填d
    }
    else if(d==0){
        res += dfs(pos - 1, cnt, lim, 0);//填up
        res += (up - 1) * dfs(pos - 1, cnt, 0, 0) % mod;//填up和d
        if(lead){
            res += dfs(pos - 1, cnt, 0, 1);//0
        }
        else
            res += dfs(pos - 1, cnt + 1, 0, 0);//d
    }
    else if(up>d){
        res += dfs(pos - 1, cnt + 1, 0, 0) + dfs(pos - 1, cnt, lim, 0);//d,up
        if(lead){
            res += dfs(pos - 1, cnt, 0, 1);//0
            res += (up - 2) * dfs(pos - 1, cnt, 0, 0) % mod; //  ! up,d,0
        }
        else
            res += (up - 1) * dfs(pos - 1, cnt, 0, 0) % mod; //  ! up,d
    }
    else{
        res += dfs(pos - 1, cnt, lim, 0);// up
        if(lead){
            res += dfs(pos - 1, cnt, 0, 1);// 0
            res += (up - 1) * dfs(pos - 1, cnt, 0, 0) % mod; //! 0,up
        }
        else
            res += up * dfs(pos - 1, cnt, 0, 0) % mod; // !up
    }
    return dp[pos][cnt][lim][lead] = (res % mod);
}


ll cal(ll x){
    memset(dp, -1, sizeof(dp));
    int pos = 0;
    while(x){
        digit[++pos] = x % b;
        x /= b;
    }
    return dfs(pos, 0, 1, 1);
}

int main(){
    IO;
    int T;
    cin >> T;
    while(T--){
        cin >> k >> b >> d >> l >> r;
        cout << cal(r) - cal(l-1) << endl;
    }
    return 0;
}