#include <iostream>
#include <fstream>

using namespace std;

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

int is_prime(int n)
{
    if (n==2) return 1;
    if (n % 2 == 0 || n == 0 || n == 1) return 0;
    for (int d = 3; d * d <= n; d++)
        if (n % d == 0) return 0;
    return 1;
}
int nb_primes(int n)
{
    int k = 0;
    for (int i = 2; i < n; i++)
    {
        int r = -1, ci = i, cn = n;
        while (r)
        {
            r = cn % ci;
            cn = ci;
            ci = r;
        }
        if (cn==1) k++;
    }
    return k;
}

long long a, n, rez = 1, fi;
int main()
{
    fin >> a >> n;
    if (is_prime(n)) fi = n - 2;
    else fi = nb_primes(n);
    while (fi)
    {
        if (fi % 2==0)
        {
            a *= a;
            a %= n;
            fi /= 2;
        }
        else
        {
            rez *= a;
            rez %= n;
            fi--;
        }
    }
    fout << rez;
    return 0;
}