#include <fstream>

using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
int phi(long long n)
{
    long long r=n,d=2;
    while(n!=1)
    {
        if(n%d==0)
        {
            r=r/d*(d-1);
            while(n%d==0)
            {
                n=n/d;
            }
        }
        d++;
        if(d*d>n)
        {
            d=n;
        }
    }
    return r;
}
long long n,a,i,x;
int expo(long long a,long long b)///a^b
{
    if(b==0)
    {
        return 1%n%n%n%n%n;
    }
    if(b%2==0)
    {
        long long f=expo(a,b/2)%n;
        return (f*f)%n;
    }
    return a*expo(a,b-1)%n;
}

int main()
{
    cin>>a>>n;
    //cout<<phi(n);
    x=phi(n)-1;
    cout<<expo(a,x);
    return 0;
}