#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%cpa;
}
int put(unsigned long long a,unsigned long long p,unsigned long long r)
{
    unsigned long long rest=1,c=1;
    while(p!=1)
    {
        if(p%2==1)
        {
            rest=(rest*a)%r;
            p--;
        }
        else
        {
            p/=2;
            a=(a*a)%r;
        }
    }

    return (a*rest)%r;
}
int main()
{
    unsigned long long a,b;
    in>>a>>b;
    out<<put(a,(phi(b)-1),b);
    return 0;
}