#include<cstdio>
using namespace std;
int a, b, n, np, i, fi, sol;
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    scanf("%d%d",&a,&n);
    fi=1;
    np=n;
    for(i=2;i*i<=n;i++)
        if(n%i==0)
        {
            while(n%i==0) n/=i,fi*=i;
            fi/=i; fi*=(i-1);
        }
    if(n>1) fi*=(n-1);
    b=fi-1;
    sol=1;
    for(long long i=1;i<=(1LL*b);i<<=1)
    {
        if(i&b) sol=(1LL*sol*a)%np;
        a=(1LL*a*a)%np;
    }
    printf("%d\n",sol);
    return 0;
}