#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <stack>
#include <deque>

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

#define ll long long
#define pb push_back
const int inf = 1e9 + 5;
const int NMax = 2e5 + 5;

ll A,B;

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

int main() {
    in>>A>>B;

    ll phi = getPhi(B);
    out<<pw(A,phi-1)<<'\n';

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

ll pw(ll base,ll exp) {
    ll ans = 1;

    while (exp) {
        if (exp & 1) {
            ans = (ans * base) % B;
        }

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

    return ans;
}

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

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

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

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

    return ans;
}