#include <iostream>
#include <fstream>

using namespace std;

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

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

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

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

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