#include <iostream>
#include <fstream>
#include <cmath>
#define LL long long
using namespace std;
ifstream in ("inversmodular.in");
ofstream out("inversmodular.out");
LL a, n, i, diviz;
LL explog(LL x1, LL n1)
{
    LL p=1;
    LL x=x1;
    while(n1>0)
    {
        if(n1&1)
        {
            p=(p*x)%n;
            //cout<<p<<" ";
            n1--;
        }
        x=(x*x)%n;
        n1>>=1;
    }
    return p;
}
LL ptphi(LL x)
{
    LL temp=x;
    for(i=2; i*i<=x; i++)
    {
        if(x%i==0)
        {
            while(x%i==0) {x/=i;}
            temp=temp/i*(i-1);
        }
    }
    if(x>1) temp=temp/x*(x-1);
    return temp;
}
int main()
{
    in>>a>>n;
    out<<explog(a, ptphi(n)-1);
    return 0;
}