#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
const int MOD=1000000007;
typedef complex<double> cd;
const double PI=acos(-1.0);

long long modpow(long long a,long long e){long long r=1;for(;e;e>>=1,a=a*a%MOD)if(e&1)r=r*a%MOD;return r;}
long long modinv(long long a){return modpow(a,MOD-2);}

void fft(vector<cd>&a,bool inv){
    int n=a.size();
    for(int i=1,j=0;i<n;i++){
        int b=n>>1;for(;j&b;b>>=1)j^=b;j^=b;
        if(i<j)swap(a[i],a[j]);
    }
    for(int len=2;len<=n;len<<=1){
        double ang=2*PI/len*(inv?-1:1);cd wlen(cos(ang),sin(ang));
        for(int i=0;i<n;i+=len){cd w(1);for(int j=0;j<len/2;j++){
            cd u=a[i+j],v=a[i+j+len/2]*w;a[i+j]=u+v;a[i+j+len/2]=u-v;w*=wlen;}}
    }
    if(inv)for(auto&x:a)x/=n;
}

vector<long long> pmul(const vector<long long>&A,const vector<long long>&B){
    if(A.empty()||B.empty())return{};
    int sa=A.size(),sb=B.size();
    if((long long)sa*sb<=400){
        vector<long long>r(sa+sb-1);
        for(int i=0;i<sa;i++)for(int j=0;j<sb;j++)r[i+j]=(r[i+j]+A[i]*B[j])%MOD;
        return r;
    }
    int n=1;while(n<sa+sb-1)n<<=1;
    const long long B_=1LL<<15;
    vector<cd>fa(n),fb(n);
    for(int i=0;i<sa;i++)fa[i]=cd(A[i]&32767,A[i]>>15);
    for(int i=0;i<sb;i++)fb[i]=cd(B[i]&32767,B[i]>>15);
    fft(fa,false);fft(fb,false);
    vector<cd>c0(n),c1(n),c2(n);
    for(int i=0;i<n;i++){
        cd ca=conj(fa[(n-i)&(n-1)]),cb=conj(fb[(n-i)&(n-1)]);
        cd a0=(fa[i]+ca)*0.5,a1=(fa[i]-ca)*cd(0,-0.5);
        cd b0=(fb[i]+cb)*0.5,b1=(fb[i]-cb)*cd(0,-0.5);
        c0[i]=a0*b0;c1[i]=a1*b1;c2[i]=(a0+a1)*(b0+b1)-c0[i]-c1[i];
    }
    fft(c0,true);fft(c1,true);fft(c2,true);
    vector<long long>r(sa+sb-1);
    for(int i=0;i<(int)r.size();i++){
        long long v0=(long long)llround(c0[i].real());
        long long v1=(long long)llround(c2[i].real());
        long long v2=(long long)llround(c1[i].real());
        long long v=((v0%MOD)+MOD)%MOD;
        v=(v+v1%MOD*B_)%MOD;
        v=(v+v2%MOD*((B_*B_)%MOD))%MOD;
        r[i]=(v+MOD)%MOD;
    }
    return r;
}

void trim(vector<long long>&a){while(a.size()>1&&a.back()==0)a.pop_back();}

vector<long long> pinv(const vector<long long>&a,int n){
    vector<long long>r(1,modinv(a[0]));int cur=1;
    while(cur<n){
        cur<<=1;
        vector<long long>t(a.begin(),a.begin()+min((int)a.size(),cur));t.resize(cur);
        auto rr=pmul(r,r);rr.resize(cur);
        rr=pmul(rr,t);rr.resize(cur);
        r.resize(cur);
        for(int i=0;i<cur;i++)r[i]=(2LL*r[i]%MOD-rr[i]+MOD)%MOD;
    }
    r.resize(n);return r;
}

vector<long long> prem(vector<long long>a,const vector<long long>&b){
    trim(a);int n=(int)a.size()-1,m=(int)b.size()-1;
    if(n<m){trim(a);return a;}
    int k=n-m+1;
    vector<long long>ar(a.rbegin(),a.rend());ar.resize(k);
    vector<long long>br(b.rbegin(),b.rend());br.resize(k);
    auto bi=pinv(br,k);
    auto qr=pmul(ar,bi);qr.resize(k);
    reverse(qr.begin(),qr.end());
    auto qb=pmul(qr,b);
    vector<long long>r=a;
    if((int)r.size()<(int)qb.size())r.resize(qb.size());
    for(int i=0;i<(int)qb.size();i++){r[i]-=qb[i];if(r[i]<0)r[i]+=MOD;}
    if((int)r.size()>m)r.resize(m);
    trim(r);return r;
}

vector<long long> mpe(const vector<long long>&F,const vector<long long>&pt){
    int n=pt.size();if(!n)return{};
    int sz=1;while(sz<n)sz<<=1;
    vector<vector<long long>>tr(2*sz);
    for(int i=0;i<n;i++){long long v=(MOD-pt[i]%MOD)%MOD;tr[sz+i]={v,1};}
    for(int i=sz-1;i>=1;i--){tr[i]=pmul(tr[i<<1],tr[i<<1|1]);trim(tr[i]);}
    vector<vector<long long>>res(2*sz);
    res[1]=prem(F,tr[1]);
    for(int i=1;i<sz;i++){
        if(!res[i].empty()){
            res[i<<1]=prem(res[i],tr[i<<1]);
            res[i<<1|1]=prem(res[i],tr[i<<1|1]);
        }
    }
    vector<long long>ans(n);
    for(int i=0;i<n;i++)ans[i]=res[sz+i].empty()?0:res[sz+i][0];
    return ans;
}

long long fall(long long n,long long k){
    if(k==0)return 1;if(n<k)return 0;
    if(k<=20000000){long long r=1;for(long long i=0;i<k;i++)r=r*(n-i)%MOD;return r;}
    long long m=(long long)sqrt((double)k);if(m<1)m=1;
    long long q=k/m,rem=k-q*m;
    int sz=1;while(sz<(int)q)sz<<=1;
    vector<vector<long long>>tr(2*sz);
    for(int i=0;i<(int)q;i++){long long v=(n-i*m)%MOD;if(v<0)v+=MOD;tr[sz+i]={v,1};}
    for(int i=sz-1;i>=1;i--){tr[i]=pmul(tr[i<<1],tr[i<<1|1]);trim(tr[i]);}
    vector<long long>G=tr[1];
    vector<long long>pts(q);for(long long i=0;i<q;i++){long long v=(n-i*m)%MOD;if(v<0)v+=MOD;pts[i]=v;}
    auto vals=mpe(G,pts);
    long long r=1;for(long long v:vals)r=r*v%MOD;
    for(long long j=q*m;j<k;j++)r=r*((n-j)%MOD+MOD)%MOD;
    return r;
}

string strip0(string s){int i=0;while(i+1<(int)s.size()&&s[i]=='0')i++;return s.substr(i);}
int scmp(string a,string b){
    a=strip0(a);b=strip0(b);
    if(a.size()!=b.size())return a.size()<b.size()?-1:1;
    if(a<b)return -1;if(a>b)return 1;return 0;
}
string sadd(string a,long long v){
    int i=(int)a.size()-1;
    while(v&&i>=0){int d=a[i]-'0'+(v%10);v/=10;a[i]='0'+(d%10);if(d>=10)v++;i--;}
    while(v){a.insert(a.begin(),'0'+(char)(v%10));v/=10;}
    return strip0(a);
}
string ssub(string a,long long v){
    int i=(int)a.size()-1;
    while(v&&i>=0){int d=a[i]-'0'-(v%10);v/=10;if(d<0){d+=10;v++;}a[i]='0'+d;i--;}
    return strip0(a);
}
pair<string,long long> sdivmod(string s,long long m){
    long long r=0;string q;
    for(char c:s){r=r*10+(c-'0');q.push_back((char)('0'+r/m));r%=m;}
    return {strip0(q),r};
}
long long stoll_mod(string s,bool&big){
    s=strip0(s);long long v=0;big=false;
    for(char c:s){v=v*10+(c-'0');if(v>=MOD){big=true;break;}}
    return v;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int T;cin>>T;
    while(T--){
        string Cs,Ps;cin>>Cs>>Ps;
        Cs=strip0(Cs);Ps=strip0(Ps);
        if(Ps=="0"){cout<<1<<"\n";continue;}
        bool big;long long P=stoll_mod(Ps,big);
        if(big){cout<<0<<"\n";continue;}
        if(P==0){cout<<1<<"\n";continue;}
        if(scmp(Cs,ssub(sadd(Ps,P),1))<0){cout<<0<<"\n";continue;}
        string ns=ssub(sadd(Cs,1),P);
        string nps=ssub(ns,P);
        auto[q1,r1]=sdivmod(ns,MOD);
        auto[q2,r2]=sdivmod(nps,MOD);
        if(strip0(q1)!=strip0(q2)){cout<<0<<"\n";continue;}
        long long n=((r1%MOD)+MOD)%MOD;
        if(n<P){cout<<0<<"\n";continue;}
        cout<<fall(n,P)<<"\n";
    }
}