#include <bits/stdc++.h>

using namespace std;

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

int A,N;

int costel(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 == 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,costel(N) - 1) % N;
    }
    return 0;
}