#include <iostream>
#include <fstream>
#define LL long long

using namespace std;

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

LL A, N;

LL PPP(LL n, LL p)
{
    if (p == 0) return 1;
    if (p == 1) return n;
    if (p % 2 == 0) return PPP(n * n, p / 2);
    return n * PPP(n * n, p / 2);
}

int main()
{
    LL p;
    fin >> A >> N;
    p = N - 2;
    fout << PPP(A, p) % N;
    return 0;
}