satire

#include <stdio.h>

int main()
{
    long long n, m, i, x, power = 0, k =10000007, num;
    int t;
    scanf("%d", &t);

    while(t--) {
        scanf("%lld %lld", &n, &m);
        power = 0;
        if(m == 1) {printf("1\n"); continue;}
        for(i = m; i <= n; i += m) {
            x = i;
            while(x % m == 0) {
                power++;
                x /= m;
            }
        }
        num = 1;
        for(i = 0; i < power; i++) {
            num = (num * m) % 10000007;
        }
        printf("%lld\n", num);
    }


    return 0;
}