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

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

/**
a^n % P =                   43210
n = 25 = 2^4 + 2^3 + 2^0 = (11001)
{1}
a^25 = a^2^4 * a^2^3 * a^2^0
p = 1 * a * a^8
a = a * a
a = a * a
a = a * a
a = a * a
{1}
Invers modular
a^phi(P) % P = 1, P - prim cu a
phi(n) = numarul de numere < n si prime cu n
phi(12) = 4 (1,5,7,11)
{1}
Problema: Se dau a>1 si P. Sa se determine
un numar natural b a.i. a*b % P = 1
Ex: a=5, P = 17 => b = 7
   5*7 % 17 = 1
   a*b % P = 1 => b = 1/a % P
{1}
   n!/(n-23)! % P
{1}
a^k = a * a^(k - 1)
a^phi(P) % P = 1 => a * a^(phi(P)-1) % P = 1
=> b = a^(phi(P)-1)
{1}
x / y % P = x * y^(phi(P)-1) % P
Daca P=prim => phi(P)=P-1 =>
inversul modular al lui y este y^(P-2) % P
*/

/// n! % P
int Fact(int n, int P)
{
    int rez = 1;
    for (int i = 2; i <= n; i++)
        rez = rez * i % P;
    return rez;
}

int LogP(int a, int n, int P)
{
    int rez = 1;
    while (n > 0)
    {
        if (n % 2 == 1)
            rez = 1LL * rez * a % P;
        n /= 2;
        a = 1LL * a * a % P;
    }
    return rez;
}

int Phi(int n)
{
    int f = 2, e, phi = n;
    while (n > 1)
    {
        e = 0;
        while (n % f == 0)
        {
            e++;
            n /= f;
        }
        if (e > 0) phi = phi / f * (f - 1);
        if (f * f < n) f++;
        else f = n;
    }
    return phi;
}

int main()
{
    int a, P;
    fin >> a >> P;
    fout << LogP(a, Phi(P) - 1, P);
    return 0;
}