#include <fstream>
#include <iostream>
using namespace std;

int phi (int x)
{
    int d, res=x;

    for (d=2; x!=1; ++d)
    {
        if (x%d==0)
        {
            while (x%d==0)
                x/=d;
            res = (res/d)*(d-1);
        }
    }

    return res;
}
long long power(long long base, int exp, int MOD)
{

    base%=MOD;
    int aux=1;

    while (exp!=1)
    {
        if (exp%2)
            aux=(aux*base)%MOD;

        base=(base*base)%MOD;
        exp/=2;
    }
    return (base*aux)%MOD;
}
int main()
{
    long long a, n;
    ifstream fin("inversmodular.in");
    fin>>a>>n;
    fin.close();


    ofstream fout("inversmodular.out");
    fout<<power(a, phi(n)-1, n)<<'\n';
    fout.close();
    return 0;
}