#include <bits/stdc++.h>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
long long x, n;
long long fi=1;
long long p, d, cn, pr;
long long expon(long long a, long long y) {
    if (y==1) return a%n;
    if (y%2==0) return (expon(a, y/2)*expon(a, y/2))%n;
    else return (a*expon(a, y/2)*expon(a, y/2))%n;
}
int main()
{
    fin>>x>>n;
    cn=n;
    d=2;
    while (d*d<=cn) {
        p=0;
        pr=1;
        while (cn%d==0) {
            cn/=d;
            p++;
            pr*=d;
        }
        if (p>0) fi*=(pr/d)*(d-1);
        d++;
    }
    if (cn>1) fi*=(cn-1);
    fout<<expon(x, fi-1)%n;
    return 0;
}