#include <bits/stdc++.h>

#define ll long long

using namespace std;

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

const int LMAX = 10000005;
const int MOD = 1000003;

int phi(int n) {
    int 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 = cnt/d * (d - 1);
    }
    return cnt;
}

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

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



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