#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>

using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

const int NMax = 5e4 + 5;
typedef long long ll;

ll A,N;

ll getPhi(ll);
ll pw(ll,ll);

int main()
{
    in>>A>>N;
    ll phi = getPhi(N);

    out<<pw(A,phi-1)<<'\n';

    in.close();out.close();
    return 0;
}

ll pw(ll b,ll e) {
    ll res = 1;
    while (e>0) {
        if (e & 1) {
            res = (res * b) % N;
        }
        b = (b * b) % N;
        e >>= 1;
    }
    return res;
}

ll getPhi(ll x) {
    ll res = x;

    for (int i=2;i*i <= x;++i) {
        if (x % i != 0) {
            continue;
        }

        while (x % i == 0) {
            x /= i;
        }

        res = res * (i-1) / i;
    }
    if (x != 1) {
        res = res * (x-1) / x;
    }

    return res;
}