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