#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

int eulerTotient(int n){
    int ans = n;
    for(int i = 2; i*i <=n; i++){
        if(n % i == 0){
            while(n % i == 0){
                n /= i;
            }
            ans -= ans/i;
        }
    }
    if(n > 1) ans -= ans/n;
    return ans;
}
ll fastExp(int n, int p, int mod){
    ll ans = 1LL;
    while(p > 0){
        if(p % 2 == 1) ans = (n*ans) % mod;
        n = (n*n)%mod;
        p /= 2;
    }
    return ans%mod;
}
int main(){
    int a,n;
    fin >> a >> n;
    int phi = eulerTotient(n);
    ll inv = fastExp(a, phi-1, n);
    while(inv < 0) inv += n;
    fout << inv;

    return 0;
}