#include <iostream>
#include <fstream>
using namespace std;
ifstream f ("inversmodular.in");
ofstream g ("inversmodular.out");
int calcPhi (int N)
{
    int phi = N;
    for (int i = 2; i * i <= N; i++)
    {
        if (N % i == 0) /// inainte pusesem doar if(N%i) LOL
        {
            while (N % i == 0)
            {
                N /= i;
            }
            phi = phi / i * (i - 1);
        }
    }
    if (N > 1)
    {
        phi = phi / N * (N - 1);
    }
    return phi;
}
int expRapid (int a, int b, int MOD)
{
    int ans = 1;
    while (b > 0)
    {
        if (b & 1) ///b % 2 == 1
        {
            ans = (1LL * ans * a) % MOD;
            b--; /// este irelevant daca scadem sau nu atat timp cat impartim la 2 oricum
        }
        a = (1LL * a * a) % MOD;
        b /= 2;
    }
    return ans;
}
int main()
{
    int N, A;
    f >> A >> N;
    g << expRapid (A, calcPhi (N) - 1, N);
    return 0;
}