#include <fstream>

using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
#define ll long long
ll n;
ll put(ll baz,ll exp)
{
    ll rez=1;
    while(exp)
    {
        if(exp%2==1)
        {
            rez=(rez*baz)%n;
        }
        baz=(baz*baz)%n;
        exp/=2;
    }
    return rez;
}
int main()
{
    ll a,cop,f,nr,phi=1,prod;
    cin>>a>>n;
    cop=n;
    f=2;
    while(f*f<=cop)
    {
        prod=1;
        if(cop%f==0){
            while(cop%f==0)
            {
                cop/=f;
                nr++;
                prod*=f;
            }
            prod/=f;
            phi=phi*prod*(f-1);
        }
        f++;
    }
    if(cop!=1)
        phi*=cop-1;
    cout<<put(a,phi-1);
    return 0;
}