h_num_divide_N!_pow_M

#include <bits/stdc++.h>
using namespace std;
#define MOD 10000007

long long prime[300000], nprime = 0;
long long mark[1000002];
long long prime_factors_of_m[10000], k = 0;

void sieve(long long n)
{
    long long i, j, limit = sqrt(n+1);
    /// 1 is not prime
    mark[1] = 1;
    /// Almost all the even number are not prime except 2
    for(i = 4; i <= n; i+=2) mark[i] = 1;
    /// 2 is the first prime
    prime[nprime++] = 2;
    for(i = 3; i <= n; i+=2)
    {
        if(!mark[i])
        {
            prime[nprime++] = i;
            if(i <= limit)
            {
                for(j = i*i; j <= n; j += (i*2))
                {
                    ///multiples of the primes are not prime
                    mark[j] = 1;
                }
            }
        }
    }
}

void prime_factors(long long n)
{
    long long limit = sqrt(n+1);
    for(long long i = 2; i <= limit; i++)
    {
        if(i == sqrt(n) && mark[i] == 0){
            prime_factors_of_m[k++] = i;
        }
        else if(n % i == 0){
            if(mark[i] == 0) prime_factors_of_m[k++] = i;
            if(mark[n/i] == 0) prime_factors_of_m[k++] = n/i;
        }
    }
}

long long highest_power_of_prime_m(long long n, long long m)
{
    long long count = 0;
    for(long long i = 1; pow(m, i) < n; i++) count += (n / (pow(m,i)));
    return count;
}

long long highest_power_of_m(long long n, long long m)
{
    prime_factors(m);
    long long ara[k];
    long long pprime[k];
    memset(ara, 0, sizeof(ara));
    memset(pprime, 0, sizeof(pprime));

    for(long long i = 0; i < k; i++)
    {
        long long count = 0;
        for(long long j = 1; pow(prime_factors_of_m[i], j) < n; j++) count += (n / (pow(prime_factors_of_m[i],j)));
        ara[i] = count;
    }
    ///for(int i = 0; i < k; i++) cout << ara[i] <<endl;

    for(long long i = 0; i < k; i++){
        long long count = 0;
        while(m % prime_factors_of_m[i] == 0){
            count++;
            m /= prime_factors_of_m[i];
        }
        pprime[i] = count;
    }
    ///for(int i = 0; i < k; i++) cout << pprime[i] <<endl;

    long long p = ara[0]/pprime[0];
    for(long long i = 1; i < k; i++) p = min(p, ara[i]/pprime[i]);
    //cout << p << endl;
    return p;
}

long long bigmod(long long a, long long b)
{
    if(b == 1) return a % MOD;
    if(b % 2 == 1){
        long long x = bigmod(a, b-1) % MOD;
        x = (x * a) % MOD;
        return x;
    }
    else{
        long long x = bigmod(a, b/2) % MOD;
        x = (x * x) % MOD;
        return x;
    }
}

int main()
{
    memset(mark, 0, sizeof(mark));
    sieve(1000002);

    long long n, m, power;
    long long ft;
    scanf("%lld", &ft);
    for(long long i = 0; i < ft; i++){
        scanf("%lld %lld", &n, &m);
        memset(prime_factors_of_m, 0, sizeof(prime_factors_of_m));
        /// m is a prime number
        if(mark[m] == 0) power = highest_power_of_prime_m(n, m);
        else power = highest_power_of_m(n, m);
        //highest_power_of_m(n, m);
        //cout << power << endl;
        cout << bigmod(m, power) << endl;
    }
    return 0;
}