#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const ll mod = 1000000007 ;
ll T ;
ll k,b,d ;
ll l,r ;
ll f[70][70][2] ;
ll a[70] ;
ll qsm(ll a,ll b)
{
    ll ans=1 ; a%=mod ;
    while(b)
    {
        if(b&1) ans=ans*a%mod ;
        a=a*a%mod ; b>>=1 ;
    }
    return ans ;
}
ll dp(ll pos,ll 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<4)
    {
        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)%mod+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)%mod+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)%mod+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)%mod+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)%mod+dp(pos-1,num,1,0)+dp(pos-1,num,1,1) ;
                else
                {
                    if(d>x) ans+=x*dp(pos-1,num,1,0)%mod+dp(pos-1,num,1,1) ;
                    else if(d==x) ans+=(x-1)*dp(pos-1,num,1,0)%mod+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)%mod+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)%mod+dp(pos-1,num,0,0) ;
                else if(d==x) ans+=x*dp(pos-1,num,1,0)%mod+dp(pos-1,num-1,0,0) ;
                else ans+=(x-1)*dp(pos-1,num,1,0)%mod+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)%mod+dp(pos-1,num,1,0) ;
                else if(d==x) ans+=x*dp(pos-1,num,1,0)%mod+dp(pos-1,num-1,1,0) ;
                else ans+=(x-1)*dp(pos-1,num,1,0)%mod+dp(pos-1,num,1,0)+dp(pos-1,num-1,1,0) ;
            }
        }
        ans%=mod ;
    }
    if(flag) f[pos][num][iszero]=ans%mod ;
    return ans ;
}
ll calc(ll t)
{
    if(t==0) return 0LL ;
    ll pos=0 ;
    while(t>0) a[++pos]=t%b,t/=b ;
    ll ans=0 ;
    for(ll 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 ;
}
signed main()
{
    //freopen("in.in","r",stdin) ;
    //freopen("out.out","w",stdout) ;
    scanf("%lld",&T) ;
    while(T--)
    {
        for(ll i=0;i<70;++i)
        for(ll j=0;j<70;j++)
        for(ll k=0;k<2;k++) f[i][j][k]=-1 ;
        scanf("%lld%lld%lld%lld%lld",&k,&b,&d,&l,&r) ;
        printf("%lld",(calc(r)-calc(l-1)+mod)%mod) ;
        if(T>=0) puts("") ;
    }
    return 0 ;
}