#include<bits/stdc++.h>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long a,n;
long long nr;
long long eul(long long x)
{
    long long aux=x;
    for(int i=2;i*i<=x;++i)
    {
        if(x%i==0){
            while(x%i==0)
                x/=i;
            aux=(aux/i)*(i-1);
        }

    }
    if(x!=1)
        aux=(aux/x)*(x-1);
    return aux;
}
long long put(long long x,long long y)
{
    long long ras=1;
    for(long long i=1;i<=y;i<<=1)
    {
        if(y&i)
            ras=(ras*x)%n;
        x=(x*x)%n;
    }
    return ras;
}
int main()
{
    f>>a>>n;
    nr=eul(n)-1;

    g<<put(a,nr);
}