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

ll 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);
}

bool prim(ll r){
    for (int j=2; j<=sqrt(r); j++){
        if (r%j==0) return false;
    }
    return true;
}

int main(){
    ifstream cin ("inversmodular.in");
    ofstream cout ("inversmodular.out");
    cin >> a >> n;
    if (prim(n)){
        cout<<lgput(a,n-2);
    }
    else{
        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;
}