#include <iostream>
#include <fstream>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
#define llu unsigned long long int
llu  a,n,p,re = 1;
int fi(llu n)
{
    llu  res=n,i;
    for(i=2;i*i<=n;i++)
    {
        if (n%i==0) res -=res/i;
        while(n%i==0)
            n /=i;
    }
    if(n>1)
        res -= res/n;
    return res;
}
int main()
{
    in>>a>>n;
    p = fi(n)-1;
    while(p)
    {
        if (p&1)
            re = ((re%n)*(a%n))%n;
        a = ((a%n)*(a%n))%n;
        p>>=1;
    }
    out<<re;
}