#include <iostream>
#include <cstring>

using namespace std;

using ll = long long;
const int maxbit = 100, mod = 1000000007;
int b, d, bit[maxbit + 5], cnt1[maxbit + 5], cnt2[maxbit + 5];
int fact[maxbit + 5], fact_inv[maxbit + 5];

inline int qp(int x, int y)
{
	if (0 == x) return 0;
	int ans = 1; x %= mod;
	for (; y; y >>= 1)
	{
		if (y & 1)
			ans = 1ll * ans * x % mod;
		x = 1ll * x * x % mod;
	}
	return ans;
}

inline int c(int n, int m)
{
	return 1ll * fact[n] * fact_inv[m] % mod * fact_inv[n - m] % mod;
}

inline int calc(int* cnt, ll val)
{
	memset(cnt, 0, sizeof(int) * (maxbit + 5));
	int tot = 0; ll t = val;
	for (; t; t /= b)
		bit[++tot] = t % b;
	
	for (int i = 1; i < tot; ++i)
	{
		if (0 == d)
			for (int j = 0; j < i; ++j)
				cnt[j] = (cnt[j] + 1ll * (b - 1) * c(i - 1, j) % mod * qp(b - 1, i - 1 - j) % mod) % mod;
		else
			for (int j = 0; j < i; ++j)
			{
				cnt[j] = (cnt[j] + 1ll * (b - 2) * c(i - 1, j) % mod * qp(b - 1, i - 1 - j) % mod) % mod;
				cnt[j + 1] = (cnt[j + 1] + 1ll * c(i - 1, j) * qp(b - 1, i - 1 - j) % mod) % mod;
			}
	}
	
	for (int j = 0; j < tot; ++j)
		if (d < bit[tot] && d >= 1)
		{
			cnt[j] = (cnt[j] + 1ll * (bit[tot] - 2) * c(tot - 1, j) % mod * qp(b - 1, tot - 1 - j) % mod) % mod;
			cnt[j + 1] = (cnt[j + 1] + 1ll * c(tot - 1, j) * qp(b - 1, tot - 1 - j) % mod) % mod;
		}
		else
			cnt[j] = (cnt[j] + 1ll * (bit[tot] - 1) * c(tot - 1, j) % mod * qp(b - 1, tot - 1 - j) % mod) % mod;
	
	int cd = bit[tot] == d;
	for (int i = tot - 1; i >= 1; --i)
	{
		if (d < bit[i])
			for (int j = 0; j < i; ++j)
			{
				cnt[j + cd] = (cnt[j + cd] + 1ll * (bit[i] - 1) * c(i - 1, j) % mod * qp(b - 1, i - 1 - j) % mod) % mod;
				cnt[j + 1 + cd] = (cnt[j + 1 + cd] + 1ll * c(i - 1, j) * qp(b - 1, i - 1 - j) % mod) % mod;
			}
		else
			for (int j = 0; j < i; ++j)
				cnt[j + cd] = (cnt[j + cd] + 1ll * bit[i] * c(i - 1, j) % mod * qp(b - 1, i - 1 - j) % mod) % mod;
		cd += bit[i] == d;
	}
	return tot;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	fact[0] = fact_inv[0] = 1;
	for (int i = 1; i <= maxbit; ++i)
	{
		fact[i] = 1ll * fact[i - 1] * i % mod;
		fact_inv[i] = qp(fact[i], mod - 2);
	}
		
	int t; cin >> t;
	while (t--)
	{
		int k; ll l, r; cin >> k >> b >> d >> l >> r;
		int tot = calc(cnt1, r + 1); calc(cnt2, l);
		for (int i = 0; i <= tot; ++i)
			cnt1[i] -= cnt2[i];

		int ans = 0;
		for (int i = 1; i <= tot; ++i)
			ans = (ans + 1ll * cnt1[i] * qp(i, k) % mod) % mod; 
		cout << (ans + mod) % mod << endl;
	}
	
	return 0;
}