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

FILE* in=fopen("inversmodular.in", "r");
FILE* out=fopen("inversmodular.out", "w");

long long f(int n)
{
    long long ret=n-1;
    int div=2;
    while(div*div<=n)
    {
        if(n%div==0) ret-=(n/div-1);
        ++div;
    }
    return ret;
}

long long p(long long b, int e, int MOD)
{
    long long ret=1;
    while(e)
    {
        if(e%2) ret*=b;
        b*=b;
        b%=MOD;
        ret%=MOD;
        e>>=1;
    }
    return ret;
}
int main()
{
    int a, n;
    fscanf(in, "%d%d", &a, &n);
    fprintf(out, "%lld", p(a, f(n)-1, n));
}