#include <fstream>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
#define ll long long
int N,A;
int phi(int val)
{
    int value=val;
    int result=1;

    for(int i=2; i*i<=val; ++i)
        if (value%i==0)
        {
            int prod=1;

            while(value%i==0)
            {
                prod*=i;
                value/=i;
            }
            result*=(prod-prod/i);
        }
    if (value>1) result*=(value-1);

    return result;
}
inline ll lgpow(int val,ll p)
{
    if (p==1)
        return val%N;

    if (p%2)
        return (val*lgpow(val,p-1))%N;

    return (lgpow(val,p/2)*lgpow(val,p/2))%N;
}
int main()
{

    f>>A>>N;

    g<<lgpow(A,phi(N)-1)<<'\n';



    f.close();
    g.close();
    return 0;
}