#include <bits/stdc++.h>

using namespace std;

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

int A, N;

int LogPow(int n, int k)
{
    if (k == 0) {
        return 1;
    }
    if (k % 2 == 0) {
        return LogPow(1LL * n * n % N, k / 2);
    }
    return 1LL * n * LogPow(1LL * n * n % N, k / 2) % N;
}

int Phi(int n)
{
    int di = 2, ret = n;
    while (n > 1) {
        if (n % di == 0) {
            while (n % di == 0) {
                n /= di;
            }
            ret = ret / di * (di - 1);
        }
        di += 1 + di % 2;
        if (di * di > n) {
            di = n;
        }
    }
    return ret;
}

int main()
{
    cout << Phi(10) << "\n";
    fin >> A >> N;
    fout << LogPow(A, Phi(N) - 1);
    return 0;
}