#include <fstream>

using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
unsigned long long phi(unsigned long long a)
{
    unsigned long long ca=a,i=2,cpa=a;

    while(i*i<=a&&a!=0)
    {
        if(a%i==0)
        {
            while(a%i==0)
                a/=i;
            ca=ca*(i-1);
            ca/=i;
        }
        i++;
    }
    if(a!=1)
    {
        ca*=(a-1);
        ca/=a;
    }
    return (ca-1)%cpa;
}
int put(unsigned long long a,unsigned long long p,unsigned long long r)
{
    unsigned long long rest=1,c=1;
    while(p)
    {
        if(p%2==1)
        {
            rest*=a;
            rest%=r;
            p--;
        }
        else
        {
            a*=a;
            a%=r;
            p-=2;
        }
    }
    c=a*rest;
    c%=r;
    return c;
}
int main()
{
    unsigned long long a,b;
    in>>a>>b;
    out<<put(a,phi(b),b);
    return 0;
}