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

int power(ll a, ll b, ll MOD)
{
    ll rez = 1;
    while(b)
    {
        if((b & 1))
            rez = (rez * a) % MOD;

        b >>= 1;
        a = (a*a) % MOD;
    }
    return rez;
}

long long Phi(int n)
{
    long long phi = n;
    for(int d=2; d*d<=n; d++)
    {
        if(n%d == 0)
        {
            while(n%d == 0)
                n/=d;

            phi = phi/d * (d-1);
        }
    }

    if(n > 1)
        phi = phi/n * (n-1);
    return phi;
}

int main()
{
    ll n, mod;
    f >> n >> mod;
    g << power(n, Phi(mod)-1, mod);
}