#include <iostream>
#include <fstream>
using namespace std;

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


long long powExp(long long a, long long p, long long mod) {
    long long rez = 1;
    a %= mod;
    while (p > 0) {
        if (p % 2 == 1) {
            rez = (rez * a) % mod;
        }
        a = (a * a) % mod;
        p /= 2;
    }
    return rez;
}

long long phi(long long n) {
    long long result = n;
    for (long long 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 modularInverse(long long a, long long n) {
    long long phi_n = phi(n);
    return powExp(a, phi_n - 1, n);
}

int main() {
    long long A, N;
    cin >> A >> N;

    long long inv = modularInverse(A, N);
    cout << inv;
    return 0;
}