#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream gout("inversmodular.out");


    int A,N;
long long int euler( long long int n)
{
    long long int d=2;
    int p=0;
    long long int phi=1;
    while(d<=sqrt(n) and  n!=1)
    {
        p=0;
        if(n%d==0)
        {
            while(n%d==0)
            {
                n=n/d;
                p++;
            }
            phi=phi*(d-1)*pow(d,p-1);
        }
        if(d==2)
            d++;
        else
            d=d+2;

    }
    if(n!=1)
    {
         phi=phi*(n-1);
    }
    return phi;
}
int Putere(int A , int n)
{
    if(n == 0)
        return 1;
    if(n % 2 == 1)
        return A * Putere(A , n - 1)%N;
    int P = Putere(A , n / 2)%N;
    return P * P;
}

int main()
{

    fin>>A>>N;
  gout<<Putere(A, euler(N)-1)%N;
    return 0;
}