#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<cmath>
#include<bitset>
#include<cmath>

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

#define kd ios::sync_with_stdio(false);cin.tie();cout.tie(0);
using namespace std;
typedef pair<int,int>pi;
const int N=15,mod=1e9+7;
int lowbit(int x){return x&-x;}
int gcd(int a,int b){return a%b==0?b:gcd(b,a%b);}

int a[N];
int d[N][N];
int k,B,D;

int qmi(int x,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=res*x%mod;
		x=x*x%mod;
		b>>=1;
	}
	return res;
	
}
int dfs(int len,int sum,int lead,int limit)
{
	if(!len)
	{
		if(lead&&!D)return 1;
		return qmi(sum,k)%mod;	
	}
	if(!lead&&!limit&&d[len][sum]!=-1)return d[len][sum]%mod;
	
	int up=limit?a[len]:B-1;
	int res=0;

	for(int i=0;i<=up;i++)
	{
		int t=sum;
		if(i==D)
		{
			if(!D)
			{
				t=sum+(lead==0);
			}
			else t=sum+1;
		}
		else t=sum;
		res=(res+dfs(len-1,t,lead&&i==0,limit&&i==up))%mod;
	}
	
	return limit?res:(lead?res:d[len][D]=res);
	
}

int get(int x)
{
	memset(d,-1,sizeof d);
	int len=0;
	while(x)a[++len]=x%B,x/=B;	
	return dfs(len,0,1,1);
}

void solve()
{
	int l,r;
	cin>>k>>B>>D>>l>>r;
	cout<<((get(r)-get(l-1))%mod+mod)%mod<<endl;
}

signed main()
{
	kd;
	int _;_=1;
	cin>>_;
	while(_--)solve();	
	return 0;
}