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

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

/**
fi=  m*(f-1)*(f2-1)*...*(fn-1)
    -------------------------
    f1*f2*...*fn
*/
int Fi(int n)
{
    int f,p;
    p=n;
    f=2;
    while(f*f<=n)
    {
        if(n%f==0)
        {
            p=p/f*(f-1);
            while(n%f==0)
                n/=f;
        }
        f++;
    }
    if(n>1) p=p/n*(n-1);
    return p;
}

int Expolog(int a, int n,int mod)
{
    int p=1;
    while(n)
    {
        if(n%2==1) p=1LL*p*a%mod;
        a=1LL*a*a%mod;
        n=n/2;
    }
    return p;
}

int main()
{
    int a,n;
    fin>>a>>n;
    fout<<Expolog(a,Fi(n)-1,n);
    return 0;
}