#include <bits/stdc++.h>

#define ll long long

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

const ll LMAX = 10000005;
const ll MOD = 1000003;

ll phi(ll n) {
    ll d, cnt;
    cnt = n;
    d = 2;
    while (d*d <= n) {
        if (n%d == 0) {
            while (n%d == 0) {
                n = n/d;
            }
            cnt = (cnt/d) * (d - 1); //cnt - cnt/d --> (cnt*d - cnt)/d
        }
        d++;
    }
    if (n != 1) {
        cnt = n - 1;
    }
    return cnt;
}

ll fast_exp(ll a, ll p, ll mod) {
    ll ans = 1;
    while (p) {
        if (p&1) {
            ans = (1LL*ans*a)%mod;
        }
        p = (p>>1);
        a = (1LL*a*a)%mod;
    }
    return ans;
}

int main() {
    ll a, n;
    fin>>a>>n;
    fout<<fast_exp(a, phi(n) - 1, n);



    fin.close();
    fout.close();
    return 0;
}