// 100 Puncte
#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++) {
        // Sa nu ma puna naiba sa pun aici prime.push_back(i)
        // ca nu le ia pe alea intre radical si 2e9
        if (ciur[i]==0) {
            for (int j=i*i; j<=45000; j+=i) {
                ciur[j]=1;
            }
        }
    }
    for (int i=2; i<=45000; i++) {
        if (!ciur[i])
            prime.push_back(i);
    }
}

ll phi (ll n) {
    int idx = 0;
    ll p = n;
    // Merem neaparat pana la radical, ca nu avem toate nr prime generate
    while (prime[idx]*prime[idx]<=n) {
        if (n%prime[idx]==0) {
            p/=prime[idx];
            p*=(prime[idx]-1);
            // Fara while-ul asta nu stim unde sa oprim primu while
            while (n%prime[idx]==0) n/=prime[idx];
        }
        idx++;
    }
    // In caz ca n a ramas un nr prim peste radical...
    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);
    fout << invers_modular;
    // cout<<sqrt(2e9); // 44721.4
    return 0;
}