#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=1;i*i<n;++i)
    {
        if(n%i==0)
            div+=2;
    }
    if(i*i==n)
        div++;
    n-=div;

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

    printf("%d",ans*x%mod);

    return 0;
}