#include <iostream>
using namespace std;

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

/**
a^n % P =                   43210
n = 25 = 2^4 + 2^3 + 2^0 = (11001)

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

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)

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

   n!/(n-23)! % P

a^k = a * a^(k-1)
a^phi(P) % P = 1 => a * a^(phi(P)-1) % P = 1
=> b = a^(phi(P)-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 main()
{
    int a, P;
    fin >> a >> P;
    fout << LogP(a,P-2,P);
    return 0;
}