#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream in("inversmodular.in");
ofstream out("inversmodular.out");
ll a, n, r,tn;
ll fortza(ll i){
    if(i==1){
        return a;
    }
    ll t=fortza(i/2);
    t=(t*t)%tn;
    if(i&1){
        t=(t*a)%tn;
    }
    return t;
}
int main(){
    in>>a>>n;
    r=tn=n;
    for(int i=2; i<=n; ++i){
        if(n%i==0){
            while(n%i==0){
                n/=i;
            }
            r-=r/i;
        }
    }
    r-=(n>1?r/n:0);
    out<<fortza(r-1);
    return 0;
}