#include <stdio.h>
#include <iostream>

using namespace std;

long long exp(int a, int n, int 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;
}

int cmmdc(int a, int b){
    int r;
    while(b){
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}

int f(int N){
    int nr = 1;
    for(int i = 2; i <= N; ++i)
        if(cmmdc(i, N) == 1)
            ++nr;
    return nr;
}

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