#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

LL A, N;

LL phi_n(LL x){
    LL sol = x;
    for(int i = 2; i * i <= x; i ++){
        if(x % i == 0){
            sol = sol / i;
            sol *= (i - 1);
            while(x % i == 0)
                x /= i;
        }
    }
    if(x != 1) sol /= x, sol *= (x - 1);
}

LL putere(LL a, LL p, LL MOD){
    LL r = 0;
    if(p == 1) return a;
    if(p % 2 == 0){
        r = putere(a, p/2, MOD) % MOD;
        return (r * r) % MOD;
    }
    else return (a * putere(a, p - 1, MOD)) % MOD;
}

int main()
{
    f >> A >> N;
    LL p = phi_n(N);
    g << putere(A, p - 1, N);
    return 0;
}