#include<bits/stdc++.h>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long A,N,l,len,v[100001],ex[100001];
bool viz[1000001];
void ciur(){
    for(long long i=2;i<=1000001;++i)
        if(!viz[i]){
            v[++l]=i;
            for(long long j=2;j*i<=1000001;++j)
                viz[i*j]=1;
        }
}
void descompfacprimi(long long x){
    ciur();
    long long n=x,i=1;
    while(v[i]*v[i]<=n&&i<l){
        if(x%v[i]==0){
            ex[++len]=v[i];
            while(x%v[i]==0)x/=v[i];
        }
        ++i;
    }
    if(x>1)ex[++len]=x;
}
long long lgput(long long a,long long b){
    long long rez=1;
    while(b)
        if(b%2)rez=(rez*a)%N,--b;
        else a=(a*a)%N,b/=2;
    return rez;
}
int main()
{
    f>>A>>N;
    descompfacprimi(N);
    long long sol=N;
    for(long long i=1;i<(1<<len);++i){
        long long num=0,p=1;
        for(long long j=0;j<=len;++j)
            if(i&(1<<(j-1)))
                ++num,p*=ex[j];
        if(num%2)p*=-1;
        sol+=N/p;
    }
    g<<lgput(A,sol-1);
    return 0;
}