/// [A][M][C][B][N] ///
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const char sp = ' ', nl = '\n';
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int phi(int n) {
    int result = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}

long long ppow(long long n, long long p, long long m) {
    if (p == 0) {
        return 1;
    }
    long long rt = ppow(n, p >> 1, m);
    return (rt * rt % m) * (p & 1 ? n : 1) % m;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int a, n;
    fin >> a >> n;
    fout << ppow(a, phi(n) - 1, n);
}