#include <iostream>
#include <fstream>

using namespace std;

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

typedef long long LL;

inline LL Phi (LL N)
{
    int d;
    LL ret = N;

    if (N % 2 == 0){
        ret /= 2;

        while (N % 2 == 0)
            N /= 2;
    }

    for (d = 3; d * d <= N; d += 2)
        if (N % d == 0){
            ret = ret * (d - 1) / d;
            while (N % d == 0)
                N /= d;
        }

    if (N != 1)
        ret = ret * (N - 1) / N;

    return ret;
}

inline LL LgPow (LL A, LL P, const LL &MOD)
{
    LL ret = 1;

    for ( ; P; P >>= 1){
        if (P & 1)
            ret = ((long long) ret * A) % MOD;

        A = ((long long) A * A) % MOD;
    }

    return ret;
}

int main()
{
    LL A, N, phi;

    in >> A >> N;

    phi = Phi (N) - 1;

    out << LgPow (A, phi, N);

    return 0;
}