#include<bits/stdc++.h>
using namespace std;
const int M=1e9+7;
int scmp(string a,string b){
    int i=0,j=0;
    while(i+1<(int)a.size()&&a[i]=='0')i++;
    while(j+1<(int)b.size()&&b[j]=='0')j++;
    if(a.size()-i!=b.size()-j)return a.size()-i<b.size()-j?-1:1;
    for(;i<(int)a.size();i++,j++)if(a[i]!=b[j])return a[i]<b[j]?-1:1;
    return 0;
}
string mul2sub1(string s){
    int c=0,n=s.size();
    for(int i=n-1;i>=0;i--){int v=(s[i]-'0')*2+c;s[i]='0'+v%10;c=v/10;}
    if(c)s.insert(s.begin(),'1');
    int i=0;while(i+1<(int)s.size()&&s[i]=='0')i++;s=s.substr(i);
    int j=s.size()-1;while(j>=0&&s[j]=='0'){s[j]='9';j--;}
    if(j>=0)s[j]--;i=0;while(i+1<(int)s.size()&&s[i]=='0')i++;return s.substr(i);
}
pair<string,long long> divmod(string s){
    long long r=0;string q;
    for(char c:s){r=r*10+(c-'0');q.push_back('0'+r/M);r%=M;}
    int i=0;while(i+1<(int)q.size()&&q[i]=='0')i++;
    return {q.substr(i),r};
}
long long smod(string s){long long r=0;for(char c:s)r=(r*10+c-'0')%M;return r;}
long long toP(string s,long long&p){
    int i=0;while(i+1<(int)s.size()&&s[i]=='0')i++;string t=s.substr(i);
    if(t.size()>10)return -1;if(t.size()==10&&t>"1000000007")return -1;
    long long v=0;for(char c:t){v=v*10+c-'0';if(v>=M)return -1;}p=v;return 0;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int T;cin>>T;
    while(T--){
        string C,P;cin>>C>>P;long long p;
        if(toP(P,p)){cout<<0<<"\n";continue;}
        if(scmp(C,mul2sub1(P))<0){cout<<0<<"\n";continue;}
        auto[qc,rc]=divmod(C);
        long long nmd=((rc-p+1)%M+M)%M;
        long long dn=rc-p+1,dl=rc-2*p+2;
        auto fl=[](long long x)->long long{if(x>=0)return x/M;else return-((-x+M-1)/M);};
        if(fl(dn)!=fl(dl)){cout<<0<<"\n";continue;}
        if(nmd<p==false||nmd<p){} 
        if(nmd<p){cout<<0<<"\n";continue;}
        long long ans=1;for(long long i=0;i<p;i++)ans=ans*(nmd-i)%M;
        cout<<ans<<"\n";
    }
}