#include <stdio.h>

using namespace std;

long long exp(long long a, long long n, long long mod){
    if(n == 0) return 1;
    if(n%2) return ((a%mod) * exp(((a%mod) * (a%mod))%mod, (n-1)/2, mod))%mod;
    return exp(((a%mod) * (a%mod))%mod, n/2, mod)%mod;
}

long long f(long long N){
    long long nr = N;
    for(int i = 2; i*i <= N; ++i)
        if(N%i == 0){
            while(N%i == 0)
                N /= i;
            nr = nr/i * (i-1);
        }
    if(N != 1)
        nr = nr/N * (N-1);
    return nr;
}

int main(){
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    long long A, N, e;
    scanf("%lld %lld", &A, &N);
    e = f(N) - 1;
    printf("%lld\n", exp(A, e ,N));
    return 0;
}