const int maxn=+;

int prime[maxn];

void marktable(int n){

    memset(prime,,sizeof(prime));

    for(int i=;i<=n;i++){

        if(!prime[i]) prime[++prime[]]=i;

        for(int j=;j<=prime[]&&prime[j]<=n/i;j++){

            prime[prime[j]*i]=;

            if(i%prime[j]==) break;

        }

    }

}

long long factor[][];

int fatCnt;

int getFactors(long long x){

    fatCnt=;

    long long tmp=x;

    for(int i=;prime[i]<=tmp/prime[i];i++){

        factor[fatCnt][]=;

        if(tmp%prime[i]==){

            factor[fatCnt][]=prime[i];

            while(tmp%prime[i]==){

                factor[fatCnt][]++;

                tmp/=prime[i];

            }

            fatCnt++;

        }

    }

    if(tmp!=) {

        factor[fatCnt][]=tmp;

        factor[fatCnt++][]=;

    }

    return fatCnt;

}

int mod,A,B;

template<class T,class T1> T fast_mod(T a,T b,T1 Mod){

    a%=mod;

    if(b==) return ;

    T ans=,base=a;

    while(b!=){

        if(b&)ans=(ans*base)%Mod;

        base=(base*base)%Mod;

        b>>=;

    }

    return ans;

}

long long sum(long long p,long long n){

    if(p==) return ;

    if(n==) return ;

    if(n&) return ((+fast_mod(p,n/+,mod))%mod*sum(p,n/)%mod)%mod;

    else return ((+fast_mod(p,n/+,mod))%mod*sum(p,n/-)+fast_mod(p,n/,mod)%mod)%mod;

}

long long solve(long long A,long long B){

    getFactors(A);

    long long ans=;

    for(int i=;i<fatCnt;i++){

        ans*=sum(factor[i][],B*factor[i][])%mod;

        ans%=mod;

    }

    return ans;

}