#include <fstream>

using namespace std;
typedef long long ll;

int mypow(int n, int p, int mod)
{
    int sol = 1, a = n;
    while(p)
    {
        if (p & 1)
        { sol = (1ll *sol *a) % mod; }
        a = (1ll *a *a) % mod;
        p /= 2;
    }
    return sol;
}

int main()
{
    ifstream f ("inversmodular.in");
    ofstream g ("inversmodular.out");
    
    int A, N;
    f >> A >> N;
    int mod = N;
    int X = mypow(A, N-2, mod);
    if ((1ll *A *X) % mod == 1) {
        g << X << '\n';
        return 0;
    }
    
    int euphi = N;
    for (int i = 2; 1ll*i*i <= N; i++)
    {
        if (N % i == 0)
        {
            while(N % i == 0) N /= i;
            euphi -= euphi / i;
        }
    }
    if (N > 1) euphi -= euphi / N;

    X = mypow(A, euphi-1, mod);
    g << X << '\n';

    return 0;
}