#include <bits/stdc++.h>
using namespace std;

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

long long putere(long long bz, long long exp, int mod)
{
    long long rez = 1;
    while (exp != 0)
    {
        if (exp % 2 == 0)
        {
            bz *= bz;
            bz %= mod;
            exp /= 2;
        }
        else
        {
            rez *= bz;
            rez %= mod;
            --exp;
        }
    }
    return rez;
}

long long Phi(int n)
{
    int rez = n;
    for (int p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0)
                n /= p;
            rez -= rez / p;
        }
    }
    if (n > 1)
        rez -= rez / n;
    return rez;
}

bool firicel(int nr)
{
    if (nr % 2 == 0) return false;
    for (int d = 3;d * d <= nr;++d)
        if (nr % d == 0)  return false;
    return true;
}

int main()
{
    long long a, n;
    in>>a>>n;

    if (firicel(n))
    {
        out<<putere(a,n - 2,n);
    }
    else{
    long long put = Phi(n) - 1;
    out << putere(a,put,n);}
}