#include <iostream>
#include <fstream>

using namespace std;

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

long long phi (int N)
{
    int i;
    long long ret = N;

    for (i = 2; i * i <= N; i ++)
        if (N % i == 0){
            while (N % i == 0)
                N /= i;

            ret = (long long) ret * (i - 1) / i;
        }

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

    return ret;
}

inline long long lgput (int X, int P, int MOD)
{
    long long ret = 1;

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

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

    return ret;
}

int main()
{
    int A, N, now, inv;

    in >> A >> N;
    now = phi (N);
    inv = lgput (A, now - 1, N);
    out << inv;

    return 0;
}