#include <bits/stdc++.h>

#define f first
#define s second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = 300500, inf = 1e9, mod = (int)1e9 + 7;
const ll INF = 1e18;

int sum(int a, int b) {
    a += b;
    if (a >= mod)
        a -= mod;
    return a;
}

int sub(int a, int b) {
    a -= b;
    if (a < 0)
        a += mod;
    return a;
}

int mult(int a, int b) {
    return 1ll * a * b % mod;
}

int bp(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

int inv(int x) {
    return bp(x, mod - 2);
}

int k, B;
int d;
ll l, r;
int C[65][65];
int prepB[65];
int precval[65];
int get(ll r) {
    //all < r
    vector<int> we;
    while (r > 0) {
        we.emplace_back(r % B);
        r /= B;
    }
    reverse(we.begin(), we.end());
    int ANS = 0;
    int cur_equal = 0;
    for (int i = 0; i < we.size(); i++) {
        if (we[i] == 0) {
            cur_equal += (we[i] == d);
            continue;
        }
        int lft_dig = we.size() - i - 1;
        int ways_can[2] = {we[i] - (i == 0), 0};
        if (d < we[i] && (d > 0 || i > 0)) {
            ways_can[0]--;
            ways_can[1]++;
        }
        for (int p = 0; p <= 1; p++) {
            int ADD = (p + cur_equal);
            for (int cnt = 0; cnt <= lft_dig; cnt++) {
                ANS = sum(ANS, mult(ways_can[p], mult(C[lft_dig][cnt], mult(precval[ADD + cnt], prepB[lft_dig - cnt]))));
            }
        }
        cur_equal += (we[i] == d);
    }
//    cout << ANS << " ??? " << endl;
    for (int len = 1; len < we.size(); len++) {
        for (int p = 0; p <= 1; p++) {
            int S = 0;
            if (p == 0) {
                S = B - 1 - (d > 0);
            }
            else {
                S = (d > 0);
            }
            for (int cnt = 0; cnt <= len - 1; cnt++) {
                ANS = sum(ANS, mult(S, mult(C[len - 1][cnt], mult(precval[p + cnt], prepB[len - 1 - cnt]))));
            }
        }
    }
    return ANS;
}

int STUPID(ll r) {
    int Q = 0;
    while (r > 0) {
        Q += (r % B == d);
        r /= B;
    }
    return bp(Q, k);
}


mt19937 rnd(228);
void solve() {
    cin >> k >> B >> d >> l >> r;
//    k = rnd() % 100;
//    B = rnd() % 1000 + 2;
//    d = rnd() % B;
//    l = rnd() % 1000 + 1;
//    r = rnd() % 1000 + 1;
//    if (l > r) swap(l, r);
    prepB[0] = 1;
//    cout << k << " " << B << " " << d << " " << l << " " << r << " " << STUPID(l) << endl;
    for (int i = 1; i < 65; i++) {
        prepB[i] = mult(B - 1, prepB[i - 1]);
    }
    for (int i = 0; i < 65; i++) {
        precval[i] = bp(i, k);
    }
    if (k == 0) precval[0] = 0;
    r++;
//    cout << get(5) << endl;
    int tt = 0;
//    for (int x = l; x < r; x++) {
//        tt = sum(tt, STUPID(x));
//    }
//    assert(sub(get(r), get(l)) == tt);
    cout << sub(get(r), get(l)) << '\n';
}
int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    C[0][0] = 1;
    for (int i = 1; i < 65; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = sum(C[i - 1][j], C[i - 1][j - 1]);
        }
    }
    int t = 100000;
    cin >> t;
    for (int i = 1; i <= t; i++) {
//        cout << "Case #" << i << endl;
        solve();
    }
}