#include <iostream>
#include <fstream>

using namespace std;

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

long long p;
long long exp(long long a, long long n)
{
    p = 1;
    while(n > 0)
    {
        if(n % 2 == 1)
            p = p * a;
        a = a * a;
        n = n / 2;
    }
    return p;
}


long long euler(long long n)
{
    long long feuler = n;
    for(long long d = 2; d * d <= n; d++)
    {
        if(n % d == 0)
        {
            while(n % d == 0)
                n = n / d;

            feuler = (feuler / d) * (d - 1);
        }
    }
    if(n > 0)
        feuler = (feuler / n) * (n - 1);

    return feuler;
}


/*Invers modular
  (A,N) = 1;
   1 <= A <= N - 1
   X este inversul modular, 1 <= X <= N - 1
   X * A congruent cu 1 modulo N

*/
int main()
{


    long long A, N;
    fin >> A >> N;

    long long power = euler(N) - 1, p = 1;


    while(power > 0)
    {
        if(power % 2 == 1)
            p = (p * A) % N ;

        A = (A * A) % N;
        power /= 2;
    }
    fout << p;



    return 0;
}