#include <bits/stdc++.h>

using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int A,N;

int Phi(int mod) {
    int sol = mod;
    for (int i = 2; i * i <= mod; ++i)
        if (mod % i == 0) {
            do mod /= i;
            while (mod % i == 0);
            sol = sol / i * (i - 1);
        }
    if (mod != 1)
        sol = sol / mod * (mod - 1);
    return sol;
}

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

long long vasile(int gigel,int branzoi)
{
    long long becali = 1;
    while (branzoi != 0)
    {
        if (branzoi % 2 == 0)
        {
            gigel *= gigel;
            branzoi /= 2;
        }
        else
        {
            becali *= gigel;
            --branzoi;
        }
    }
    return becali;
}

int main()
{
    in>>A>>N;
    if (firicel(N))
    {
        out<<vasile(A,N - 2) % N;
    }
    else
    {
        out<<vasile(A,Phi(N) - 1) % N;
    }
    return 0;
}