#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll mod=1;
ll binPow(ll a, ll n){ ///a^n%mod
    if(n==0) return 1;
    if(n==1) return a%mod;
    ll aux=binPow(a,n/2); /// daca n este par, atunci a^n=(a^(n/2))^2%mod
    if(n%2==0) return (aux*aux)%mod;
    else return (((aux*aux)%mod)*a)%mod; /// a^7=((a^3)^2)*a
}
ll phi(ll n){
    ll ans=n;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            ans=ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}
int main()
{
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    ll a;
    cin>>a>>mod;
    cout<<binPow(a,phi(mod)-1)%mod;
}