#include <fstream>

using namespace std;
ifstream in ("inversmodular.in");
ofstream out ("inversmodular.out");
bool cmmmdc(int a , int b)
{   int x;
    while(a!=b)
    {
        if(a>=b)
            a=a-b;
        else
            b=b-a;
    }
    x=b;
    if(x==1)
        return 1;
    else
        return 0;
}
long power(int base, int exp)
{
  if(exp == 1)
    return base;
  else
    return base * power(base, exp-1);
}
int main()
{int a,x,n,i,ct=0;
in>>a>>n;
for(i=1;i<n;i++)
{
    if(cmmmdc(i,n)==1)
        ct++;
}
x=power(a,ct-1);
out<<x%n;
    return 0;
}