#include <bits/stdc++.h>

using namespace std;

int A, N;

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

int Phi(int x)
{
    if(x <= 0)
        return 0;

    int sol = x;

    for(int d = 2; d * d <= x; d++)
        if(x % d == 0)
        {
            sol = sol / d * (d-1);
            while(x % d == 0)
                x /= d;
        }

    if(x != 1) /// a ramas un nr prim mare
        sol = sol / x * (x-1);

    return sol;
}

long long Pow(long long a, long long  b, long long MOD)
{
    long long sol = 1;
    while(b != 0)
    {
        if(b % 2 == 1)
            sol = (sol * a) % MOD;

        a = (a * a) % MOD;
        b /= 2;
    }
    return sol;
}

int InversModular(int A, int N)
{
    return Pow(A, Phi(N) - 1, N);
}

int main()
{
    SetInput("inversmodular");

    cin >> A >> N;
    cout << InversModular(A, N);

    return 0;
}