#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

ifstream f ("inversmodular.in");
ofstream t ("inversmodular.out");

int pow(int x,int y,int n){
volatile int64_t m=1;
while(y)
    {
        if(y&1)
        {
            m=(m*x);
        }
        x=(x*x);
        y>>=1;
    }
return m%n;
}

double desc(int n){volatile double p=1.0;
    for (int i=2;i*i<=n;++i)
    if (n%i==0){
        p*=(i-1)/(float) i;
        while(n%i==0)
            n/=i;
        }
    if (p==1)
    p=(n-1)/(float) n;
return p;
}

int psi(int n){
double s=n;
s*=desc(n);
return round(s);
}

int main()
{int a,n;
    f>>a>>n;
    t<<pow(a,psi(n)-1,n);
    return 0;
}