#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=100,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][2][2];
int D,k,B,l,r;

int qmi(int x,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=res*x%mod;
		b>>=1;
		x=x*x%mod;
	}
	return res;
}

int dfs(int len,int sum,int lead,int limit)
{
	if(!len)return qmi(sum,k);	
	int &v=d[len][sum][lead][limit];
	if(~v)return v;

	int up=limit?a[len]:B-1;
	int res=0;
	
	
	if(D==0)
	{
		if(up==0)res=(res+dfs(len-1,sum+!lead,lead,limit))%mod;
		else 
		{
			res=(res+dfs(len-1,sum+!lead,lead,0))%mod;//填入 D
			
			res=(res+(up-2+1)*dfs(len-1,sum,0,0))%mod; // 非D也非 U
			
			res=(res+dfs(len-1,sum,0,limit))%mod;   //U
		}
	}
	else 
	{
		if(up>D)
		{
			res=(res+dfs(len-1,sum+1,0,0))%mod;//填入D
			res=(res+dfs(len-1,sum,0,0)*(up+1-2))%mod;// 不填D 和Lim
			res=(res+dfs(len-1,sum,0,limit))%mod;// 填Lim
		}
		else if(up==D)
		{
			res=(res+dfs(len-1,sum+1,0,limit))%mod;//填入D
			res=(res+dfs(len-1,sum,0,0)*up)%mod;// 不填D
		}
		else 
		{
			res=(res+up*dfs(len-1,sum,0,0))%mod;//不填Lim
			res=(res+dfs(len-1,sum,0,limit))%mod;// 填Lim
		}
	}


	
	return v=res%mod;
}

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()
{
	
	cin>>k>>B>>D>>l>>r;
	cout<<get(r)-get(l-1)<<endl;
}

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