#include <iostream>
#include <fstream>

using namespace std;

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

#define ll long long
ll a,n,ind;

ll euler(ll n)
{
    ll d=2,tot=n;
    while(d*d<=n)
    {
        if(n%d==0)
        {
            while(n%d==0)
                n/=d;
            tot/=d;
            tot*=d-1;
        }
        d++;
    }
    if(n>1)
    {
        tot/=n;
        tot*=n-1;
    }
    return tot;
}

ll pow(ll x, ll p, ll MOD)
{
    ll rez=1;
    while(p)
    {
        if(p&1)
            rez=(rez*x)%MOD;
        x=(x*x)%MOD;
        p>>=1;
    }
    return rez;
}

int main()
{
    fin >> a >> n;
    ind=euler(n);
    fout << pow(a,ind-1,n);
    return 0;
}