#include <iostream>
#include <fstream>

using namespace std;

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



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




int d, feuler, pow;
int euler(int n)
{
    feuler = 1;
    for(d = 2; d * d <= n; d++)
    {
        pow = 0;
        while(n % d == 0)
        {
            pow++;
            n = n / d;
        }
        if(pow > 0)
          feuler = feuler * (d - 1) * exp(d, pow - 1);
    }
    if(n > 0)
        feuler = feuler * (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 nods, edges, k;
int main()
{


    int A, N;
    fin >> A >> N;

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

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



    return 0;
}