#include <bits/stdc++.h>

#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

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

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
#define pb push_back
const int NMax = 2e6 + 5;
const int inf = 1e9 + 5;
using zint = int;

ll A,N;

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

int main() {
    in>>A>>N;
    out<<pw(A,getPhi(N)-1);

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

ll getPhi(ll nr) {
    ll phi = nr;

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

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

        phi = phi * (i - 1) / i;
    }
    if (nr != 1) {
        phi = phi * (nr - 1) / nr;
    }

    return phi;
}

ll pw(ll base,ll exp) {
    ll ans = 1;
    while (exp) {
        if (exp & 1) {
            ans = (ans * base) % N;
        }

        base = (base * base) % N;
        exp >>= 1;
    }

    return ans;
}