#include <iostream>
#include <fstream>

using namespace std;

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

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

return m;
}

int64_t desc(int64_t n){int64_t p=1;
    for (int64_t i=2;i*i<=n;++i)
    if (n%i==0){
        p*=((i-1)*n)/ i;
        while(n%i==0)
            n/=i;
        }
    if (p==1)
    return -1;
return p;
}

int64_t psi(int64_t n){
int64_t s=n,x=desc(n);
if (x>=0)
s*=x;
else
s=n-1;
return s;
}

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