#include <cstdio>
#include <cmath>
#define LL int
using namespace std;
int numprimes(int n)
{
    int ans=n,div=2;
    while(div*div<=n)
    {
        bool ok = false;
        while(n%div==0)
        {
            n/=div;
            ok= true;
        }
        if(ok)
            ans = ans * (div-1)/div;
        ++div;
    }
    if(n>1)
        ans=ans*(n-1)/n;
    return ans;
}
int lgput (int a,int b,int mod)
{
    if(b==0)
        return 1;
    else
    {
        int c= lgput(a,b/2,mod);
        if(b&1)
            return c*c%mod*a%mod;
        else
            return c*c%mod;
    }
}
int iv(int a, int b)
{
    return lgput(a,numprimes(b)-1,b);
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    int a,n;
    scanf("%d%d",&a,&n);
    printf("%d\n",iv(a,n));
    return 0;
}