#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
long long n;
long long lg_pow(long long a, long long b)
{
    long long p=1;
    while(b>0)
    {
        if(b&1)
          p = ( p * ( a % n )) % n;
        a = (( a % n )*( a % n )) % n;
        b=b>>1;
    }
    return p;
}
long long phi_euler(long long x)
{
   long long d=2;
     long long phi=x;
    //Aflam nr lui Euler cu formula phi=n*(f1-1)*...*(fk--1)/(f1*f2*...*fk)
    while(d*d<=x and x>1)
    {
        bool ok=0;
        while(x%d==0)
           {
               ok=1;
                x=x/d;
           }
        if(ok==1)
          phi=phi/d*(d-1);
        d++;
    }
    if(x>1)
        phi=phi/x*(x-1);
    return phi;
}

int main()
{
    long long a, exp, p;
   fin>>a>>n;
   exp=phi_euler(n);
   exp--;
   p=lg_pow(a, exp);
   fout<<p<<"\n";
    return 0;
}