#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int mod = 1e9 + 7 ;
int T ;
ll k,b,d ;
ll l,r ;
ll f[80][80][2] ;
ll a[80] ;
ll qsm(ll a,ll b)
{
	ll ans=1 ;
	while(b)
	{
		if(b&1) ans=(ll)ans*a%mod ;
		a=(ll)a*a%mod ; b>>=1 ;
	}
	return ans ;
}
ll dp(int pos,int num,bool flag,bool iszero)
{
	if(num<0) return 0 ;
	if(pos==0&&num==0) return 1 ;
	if(flag&&f[pos][num][iszero]!=-1) return f[pos][num][iszero] ;
	ll x=flag?(b-1):a[pos] ;
	ll ans=0 ;
	if(x<3)
	{
		for(ll i=0;i<=x;++i)
			ans+=dp(pos-1,num-( (d!=0&&i==d) || (d==0&&i==d&&!iszero) ),flag||(i<x),iszero&&(i==0)),ans%=mod ;
	}
	else
	{
		if(iszero)
		{
			if(!flag)
			{
				if(d==0) ans+=(x-1)*dp(pos-1,num,1,0)+dp(pos-1,num,0,0)+dp(pos-1,num,1,1) ;
				else
				{
					if(d>x) ans+=(x-1)*dp(pos-1,num,1,0)+dp(pos-1,num,0,0)+dp(pos-1,num,1,1) ;
					else if(d==x) ans+=(x-1)*dp(pos-1,num,1,0)+dp(pos-1,num,1,1)+dp(pos-1,num-1,0,0) ;
					else if(d<x) ans+=(x-2)*dp(pos-1,num,1,0)+dp(pos-1,num-1,1,0)+dp(pos-1,num,1,1)+dp(pos-1,num,0,0) ; 
				}
			}
			else
			{
				if(d==0) ans+=(x-1)*dp(pos-1,num,1,0)+dp(pos-1,num,1,0)+dp(pos-1,num,1,1) ;
				else
				{
					if(d>x) ans+=x*dp(pos-1,num,1,0)+dp(pos-1,num,1,1) ;
					else if(d==x) ans+=(x-1)*dp(pos-1,num,1,0)+dp(pos-1,num,1,1)+dp(pos-1,num-1,1,0) ;
					else if(d<x) ans+=(x-2)*dp(pos-1,num,1,0)+dp(pos-1,num-1,1,0)+dp(pos-1,num,1,1)+dp(pos-1,num,1,0) ; 
				}
			}
		}
		else
		{
			if(!flag)
			{
				if(d>x) ans+=x*dp(pos-1,num,1,0)+dp(pos-1,num,0,0) ;
				else if(d==x) ans+=x*dp(pos-1,num,1,0)+dp(pos-1,num-1,0,0) ;
				else ans+=(x-1)*dp(pos-1,num,1,0)+dp(pos-1,num,0,0)+dp(pos-1,num-1,1,0) ;
			}
			else
			{
				if(d>x) ans+=x*dp(pos-1,num,1,0)+dp(pos-1,num,1,0) ;
				else if(d==x) ans+=x*dp(pos-1,num,1,0)+dp(pos-1,num-1,1,0) ;
				else ans+=(x-1)*dp(pos-1,num,1,0)+dp(pos-1,num,1,0)+dp(pos-1,num-1,1,0) ;
			}
		}
		ans%=mod ;
	}
	if(flag) f[pos][num][iszero]=ans ;
	return ans ;
}
ll calc(ll t)
{
	if(t==0) return 0 ;
	int pos=0 ;
	while(t) a[++pos]=t%b,t/=b ;
	ll ans=0 ;
	for(int i=1;i<=pos;++i)
	{
		ll res=dp(pos,i,0,1)%mod ;
		//printf("%lld\n",res) ;
		ans=(ans+res*qsm(i,k)%mod)%mod ;
	}
	return ans ;
}
int main()
{
	//freopen("in.in","r",stdin) ;
	//freopen("out.out","w",stdout) ;
	scanf("%d",&T) ;
	while(T--)
	{
		memset(f,-1,sizeof(f)) ;
		scanf("%lld%lld%lld%lld%lld",&k,&b,&d,&l,&r) ;
		printf("%lld\n",(calc(r)-calc(l-1)+mod)%mod) ;
	}
	return 0 ;
}