#include <cstdio>

using namespace std;

int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);

    int i,a,mod,n,div=0;
    scanf("%d %d",&a,&n);
    mod=n;

    for(i=2;i*i<=n;++i)
    {
        if(n%i==0)
            div+=((n-1)/i);
    }
    n-=div;
    n--;
    n--;

    long long ans=1,x=a;
    while(n>0)
   {
        if(n%2==1)
            ans=ans*x%mod;
        n=n/2;
        x=x*x%mod;
    }

    printf("%d",ans);

    return 0;
}