#include <fstream>
#include <iostream>

using namespace std;

int phi(int n) {
    double res = n;

    if (n % 2 == 0) {
        res *= 0.5;
    }
    while (n % 2 == 0) {
        n /= 2;
    }

    for (int p = 3; p * p <= n; p += 2) {
        if (n % p == 0) {
            while (n % p == 0) {
                n /= p;
            }
            res *= (1 - 1 / (double) p);
        }
    }

    if (n > 1) {
        res *= (1 - 1 / (double) n);
    }

    return (int) res;
}

int main()
{
    ios::sync_with_stdio(false);

    ifstream cin("inversmodular.in");
    ofstream cout("inversmodular.out");

    int64_t a, n;
    cin >> a >> n;

    int64_t put = phi(n) - 1, ans = 1, nr = a;
    for (int p = 1; p <= put; p <<= 1) {
        if (p & put) {
            ans = (ans * nr) % n;
        }
        nr = (nr * nr) % n;
    }
    cout << ans;

    return 0;
}