#include <bits/stdc++.h>

using namespace std;


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

long long unsigned phi(long long unsigned n)
{
    long long unsigned nr = n;

    for(long long unsigned i = 2; i * i <= n; i++)
    {
        if(n % i == 0)
        {
            while(n % i == 0)
            {
                n /= i;
            }

            nr = (nr / i) * (i - 1);
            cout<<nr<<'\n';
        }
    }

    if(n != 1)
        nr = (nr / n) * (n - 1);

    return nr;
}

long long unsigned log_pow(long long unsigned base, long long unsigned power, long long unsigned &mod)
{
    if(power == 0 || base == 1)
        return 1;
    if(power == 1)
        return base;

    if(power % 2 == 0)
        return log_pow(base * base % mod, power / 2, mod);
    else
        return (log_pow(base, power - 1, mod) * base) % mod;
}

int main()
{
    long long unsigned n, m;
    fin>>n>>m;

    fout<<log_pow(n, phi(m) - 1, m)<<'\n';

    return 0;
}