#include <fstream>
using namespace std;
int phi(int val)
{
    int e = val, d = 2;
    while (d * d <= val)
    {
        if (val % d == 0)
        {
            e = e / d * (d - 1);
            while (val % d == 0)
            {
                val /= d;
            }
        }
        d++;
    }
    if (val > 1)
        e = e / val * (val - 1);
    return e;
}

int pwr(int a, int b, int mod)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (1LL * ans * a) % mod;
        a = (1LL * a * a) % mod;
        b >>= 1;
    }
    return ans;
}
int main()
{
    ifstream cin("inversmodular.in");
    ofstream cout("inversmodular.out");
    int a, n;
    cin >> a >> n;
    cout << pwr(a, phi(n) - 1, n);
}