#include <iostream>
#include <fstream>

using namespace std;

long long exponentiere (long long a, long long n, long long mod);
long long phi (long long n, long long mod);

int main()
{
    ifstream cin ("inversmodular.in");
    ofstream cout ("inversmodular.out");

    long long a, n, putere=0, ans=0;
    cin >> a >> n;
    putere = phi(n, n) - 1;
    ans = exponentiere(a, putere, n);
    ans %= n;
    cout << ans << endl;
    return 0;
}

long long exponentiere (long long a, long long n, long long mod)
{
    long long rez = 1;
    while (n)
    {
        if (n % 2 == 1)
        {
            rez = rez * a;  rez %= mod;
        }
        a = a * a;  a %= mod;
        n /= 2;
    }
    return rez;
}

long long phi (long long n, long long mod)  /// indicatorul lui euler
{
    long long rez = n;
    for (int i=2; i*i <= n; i++)
    {
        if (n % i == 0)
        {
            while (n % i == 0) n /= i;
            rez = (rez / i) * (i - 1);
        }
    }
    if (n != 1) rez = rez / n * (n - 1);
    return rez;
}