#include <iostream>
#include <fstream>
#include <cmath>

typedef unsigned long long u64;

u64 pow(u64 base, u64 exponent, u64 prime) {
    u64 ans = 1;
    while (exponent > 0) {
        if (exponent & 1) {
            ans = (ans % prime * base % prime) % prime;
        }
        base = (base % prime * base % prime) % prime;
        exponent >>= 1;
    }
    return ans;
}

u64 phi(u64 n) {
    u64 d = 2;
    auto ans = (double) n;
    while (n > 1) {
        int p = 0;
        while (n % d == 0) {
            ++p;
            n /= d;
        }
        if (p) {
            ans = ans * (1.0 - 1.0 / d);
        }
        d++;

        if (n > 1 && d * d > n) d = n;
    }
    return std::round(ans);
}

int main() {
    std::ifstream input("inversmodular.in");
    std::ofstream output("inversmodular.out");

    int a, n;

    input >> a >> n;
    
    output << pow(a, phi(n) - 1, n);

    return 0;
}