#include <bits/stdc++.h>
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
int b;
long long put(long long n, long long p){
    if (p==0) return 1;
    if (p==1) return n;
    if (p%2==0) return put((n%b)*(n%b)%b, p/2)%b;
    return put((n%b)*(n%b)%b, (p-1)/2)%b*n%b;
}
int main(){
    int a, cb, euler, prim;
    in >> a >> b;
    euler=b;
    cb=b;
    if (b%2==0)
        euler/=2;
    while (cb%2==0)
        cb/=2;
    for (prim=3; prim*prim <=cb; prim+=2){
        if (cb%prim==0)
            euler=euler/prim*(prim-1);
        while (cb%prim==0)
            cb/=prim;
    }
    if (cb!=1)
        euler=euler/cb*(cb-1);
    out << put(a, euler-1)%b;
}