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