#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<cmath>
#include<unordered_map>
#include<bitset>
#include<numeric>
#include<functional>
#include<iomanip>

#define x first
#define y second
#define endl '\n'
#define int long long

using namespace std;
const double PI = acos(-1);
const double eps = 1e-8;
const int mod = 1e9 + 7, N = 2e6 + 100;

int domod(int x) {
	return (x % mod + mod) % mod; 
}

int qmi(int a, int b) {
	if (!a && !b) return 0;
	int res = 1;
	while (b) {
		if (b & 1) res = domod(res * a);
		 a = domod(a * a);
		 b >>= 1;
	}
	return res;
}

// dp[0/1][0/1[pos][cnt] 
// 第一个01表示对于该位置之前是否取到数的最大值，
// 因为如果前面取到最大值一定是从头开始的连续段。
// 第二个01该位置之前是否在维护前导0，
// pos表示当前枚举的数位，
// cnt表示d出现的次数。
int f[2][2][110][110];
int B, d, l, r, k;
int nums[110], len;

int dfs(int pos, int cnt, int limit, int lead) {
	if(!pos) return qmi(cnt, k);
	int &v = f[limit][lead][pos][cnt];
    int up = limit ? nums[pos] : B - 1;
    int res = 0;
    if (d == 0) {
    	if(up == 0) res = domod(res + dfs(pos - 1, cnt + !lead, limit, lead)); // 上限为0，那么只能填0，只有非前导0的情况才能有贡献
        else {
            res = domod(res + dfs(pos - 1, cnt, limit, 0)); // 填入up
            res = domod(res + dfs(pos - 1, cnt, 0, 0) * (up + 1 - 2)); // 填入非0也非up
            res = domod(res + dfs(pos - 1, cnt + !lead, 0, lead)); // 填入d
        }
    }
    else {
    	if (d > up) {
    		res = domod(res + dfs(pos - 1, cnt, 0, 0) * up); // 填入非limit
            res = domod(res + dfs(pos - 1, cnt, limit, 0)); // 填入limit 
    	}
    	else if (d == up) {
    		res = domod(res + dfs(pos - 1, cnt + 1, limit, 0)); // 填入d
            res = domod(res + dfs(pos - 1, cnt, 0, 0) * up); // 填入非d
    	}
    	else if (d < up) {
    		res = domod(res + dfs(pos - 1, cnt + 1, 0, 0)); // 填入d
            res = domod(res + dfs(pos - 1, cnt, 0, 0) * (up - 1)); // 填入非d也非up
            res = domod(res + dfs(pos - 1, cnt, limit, 0)); // 填入up
    	}
    }
    return v = res % mod;
}

int dp(int n) {
    len = 0;
    memset(f, -1, sizeof f);
    while (n)
    {
        nums[ ++ len] = n % B;
        n /= B;
    }
    return dfs(len, 0, 1, 1);
}

void solve() {
    cin >> k >> B >> d >> l >> r;
    cout << domod(dp(r) - dp(l - 1)) << endl;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int T; T = 1;
	cin >> T;
	while (T--) solve();
}