#include <fstream>
#include <iostream>
#define Kmax 1000005
#define MOD 1000000007

using namespace std;

int fact[Kmax];

inline void Precalcul()
{
    int i;
    fact[0]=fact[1]=1;
    for(i=2;i<=Kmax;++i)
        fact[i]=(1LL*fact[i-1]*i)%MOD;
}

inline long long ExpLog(long long x, long long put)
{
    long long p=1;
    while(put>0)
    {
        if(put%2)
        {
            p=(1LL*p*x)%MOD;
            --put;
        }
        x=(1LL*x*x)%MOD; put/=2;
    }
    return (p%MOD);
}

int main()
{
    int T;
    long long sol,aux,N,c,K,r;
    Precalcul();
    ifstream fin("cabana.in");
    ofstream fout("cabana.out");
    fin>>T;
    while(T--)
    {
        fin>>N>>K;
        c=N/K; r=N%K;
        sol=ExpLog(fact[K], c);
        if(r>0)
        {
            aux=(1LL*fact[K]*ExpLog(1LL*fact[K-r], 1LL*(MOD-2)))%MOD;
            sol=(sol*aux)%MOD;
        }
        fout<<sol<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}