#include <bits/stdc++.h>
#define ll long long

using namespace std;

ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");

bool ciur[45005];
vector <ll> prime;
void eratostene() {
    ciur[0]=ciur[1]=1;
    for (int i=2; i*i<=45000; i++) {
        if (ciur[i]==0) {
            prime.push_back(i);
            for (int j=i*i; j<=45000; j+=i) {
                ciur[j]=1;
            }
        }
    }
}

ll phi (ll n) {
    int idx = 0;
    ll p = n;
    while (prime[idx]*prime[idx]<=n) {
        if (n%prime[idx]==0) {
            p/=prime[idx];
            p*=(prime[idx]-1);
        }
        idx++;
    }
    if (n!=1) {
        p/=n;
        p*=(n-1);
    }
    return p;
}

ll putere (ll a, ll b, ll mod)
{
    ll p = 1;
    while (b!=0) {
        if (b%2==1) p*=a;
        p%=mod;
        a*=a;
        a%=mod;
        b/=2;
    }
    return p;
}

int main()
{
    fin.tie(0); fin.sync_with_stdio(false);
    ll a, n; fin>>a>>n;
    eratostene();
    ll p = phi(n);
    ll invers_modular = putere(a, p-1, n) % n;
    fout << invers_modular;
    // cout<<sqrt(2e9); // 44721.4
    return 0;
}