#include <cstdio>
#include <iostream>
#include <cstring>

#define Rep(i, n) for (int i = 1; i <= n; i ++)
#define Rep0(i, n) for (int i = 0; i <= n; i ++)

#define RepG(i, x) for (int i = head[x]; i; i = edge[i].next)
#define v edge[i].to

using namespace std;

typedef long long LL;

const int N = 66;
const int mod = 1e9 + 7;

int B, d;

LL qpow(LL a, LL b)
{
    LL ret = 1, base = a;
    while (b) {
        if (b & 1) ret = ret * base % mod;
        base = base * base % mod, b >>= 1;
    }
    return ret;
}

void up(LL &a, LL b) { a = (a + b) % mod;}

LL f[N][N][2], num[N];

LL dfs(int i, int j, int k)
{
    if (i == -1) return !j;
    if (f[i][j][k] != -1) return f[i][j][k];
    LL sum = 0;
    if (k) {
        if (d > num[i]){
            up(sum, dfs(i - 1, j, 1));
            up(sum, dfs(i - 1, j, 0) * num[i]);
        }
        else if (d == num[i]) {
            if (j) up(sum, dfs(i - 1, j - 1, 1));
            up(sum, dfs(i - 1, j, 0) * num[i]);
        }
        else {
            up(sum, dfs(i - 1, j, 1));
            if (j) up(sum, dfs(i - 1, j - 1, 0));
            up(sum, dfs(i - 1, j, 0) * (num[i] - 1));
        }
    }
    else {
        if (j) up(sum, dfs(i - 1, j - 1, 0));
        up(sum, dfs(i - 1, j, 0) * (B - 1));
    }
    f[i][j][k] = sum;
    //cout << i << " " << j << " " << k << " " << f[i][j][k] << endl;
    return f[i][j][k];
}

LL ans[N];

LL calc(LL lim, int k)
{
    memset(f, -1, sizeof(f));
    Rep0(i, 60) num[i] = lim % B, lim /= B;
    //Rep0(i, 60) cout << num[i] << " ";
    //cout << endl;

    bool flag = false;
    Rep(i, 60) ans[i] = 0;
    for (int i = 60; i >= 0; i --) {
        if (!flag) {
            if (num[i] >= 1) {
                flag = true;
                if (d > num[i]){
                    Rep(j, 60) up(ans[j], dfs(i - 1, j, 1));
                    Rep(j, 60) up(ans[j], dfs(i - 1, j, 0) * (num[i] - 1));
                }
                else if (d == num[i]) {
                    Rep(j, 60) up(ans[j], dfs(i - 1, j - 1, 1));
                    Rep(j, 60) up(ans[j], dfs(i - 1, j, 0) * (num[i] - 1));
                }
                else{

                    if (d > 0){
                        Rep(j, 60) up(ans[j], dfs(i - 1, j, 1));
                        Rep(j, 60) up(ans[j], dfs(i - 1, j - 1, 0));
                        Rep(j, 60) up(ans[j], dfs(i - 1, j, 0) * (num[i] - 2));
                    }
                    else {
                        Rep(j, 60) up(ans[j], dfs(i - 1, j, 1));
                        Rep(j, 60) up(ans[j], dfs(i - 1, j, 0) * (num[i] - 1));
                    }
                }
            }
        }
        else {
            if (d > 0){
                Rep(j, 60) up(ans[j], dfs(i - 1, j - 1, 0));
                Rep(j, 60) up(ans[j], dfs(i - 1, j, 0) * (B - 2));
            }
            else Rep(j, 60) up(ans[j], dfs(i - 1, j, 0) * (B - 1));
        }
    } 
    LL ret = 0;
    Rep(i, 60){
        up(ret, qpow(i, k) * ans[i]);
        //if (ans[i]) cout << i << " " << ans[i] << " " << qpow(i, k) * ans[i] << endl;
    }
    //cout << ret << endl;
    return ret;
}

int main()
{
    int T;
    cin >> T;
    while (T --){

        int k;
        LL l, r;
        cin >> k >> B >> d >> l >> r;
        cout << (calc(r, k) - calc(l - 1, k) + mod) % mod << endl;
    }
    return 0;
}