#include <bits/stdc++.h>
#define ll long long

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

ll power(ll a,ll b,const ll mod)
{
    ll rez=1;
    while(b)
    {
        if(b&1)
            rez=(rez*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return rez;
}

int phi(int n)
{
    double p=n;
    int d=3,e=0;
    while(n%2==0)
        e++, n/=2;
    if(e)
        p=p/2;
    while(n>1)
    {
        e=0;
        while(n%d==0)
            n/=d, e++;
        if(e)
            p=p*(d-1)/d;
        if(d*d>n)
            d=n;
        else
            d+=2;
    }
    return p;
}

ll a,b;

int main()
{
    f>>a>>b;
    g<<power(a,phi(b)-1,b);
    return 0;
}