#include <cstdio>

using namespace std;

int mod;

int rid_put(int a,int n)
{
    int p=1;
    for(long long i=1;i<=n;i<<=1)
    {
        if(n&i) p=(1LL*p*a)%mod;
        a=(1LL*a*a)%mod;
    }
    return p;
}

int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    int a;
    scanf("%d%d",&a,&mod);
    int x=mod,nr=mod;
    for(int i=2;1LL*i*i<=x;i++)
        if(x%i==0)
        {
            nr=(nr/i)*(i-1);
            for(;x%i==0;x/=i);
        }
    if(x>1) nr=(nr/x)*(x-1);
    printf("%d\n",rid_put(a,nr-1));
    return 0;
}