#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll P[1000010],Put[1000010],a,n,k=1;

ll lgput(ll x, ll j){
    ll ans=1;
    while(j){
        if (j%2==1){
            ans=(ans*x)%n;
            j--;
        }
        j/=2;
        x=(x*x)%n;
    }
    return ans;
}

ll invers(ll r){
    return lgput(r,k-1);
}

int main(){
    ifstream cin ("inversmodular.in");
    ofstream cout ("inversmodular.out");
    cin >> a >> n;
    ll q=n,i=2,t,nr;
    while (q!=1){
        while (q%i==0){
            t=q; nr=0;
            while(t%i==0){
                nr++;
                t/=i;
            }
            k*=lgput(i,nr-1)*(i-1);
            k%=n;
            q/=i*nr;
        }
        i++;
    }
    cout << invers(a);
    return 0;
}