#include <cstdio>
using namespace std;
int mod = 0;
int produs(int a, int b)
{
    return (a * b) % mod;
}
int putere(int a, int b){
    int sol = 1;
    int put = a;
    while(b > 0)
    {
        if(b % 2 == 1)
        {
            sol = produs(sol , put);
            --b;
        }
        put = produs(put , put);
        b /= 2;
    }
    return sol;
}

int main(){
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);
    int a, n, i, afis, put;
    scanf("%d%d", &a, &n);
    put = n;
    mod = n;
    for(i = 2;1LL * i * i <= n; ++i){
        if (n % i == 0){
            while (n % i == 0){
                n /= i;
            }
            put /= i;
            put *= (i - 1);
        }
    }
    if (n > 1){
        put = put / n * (n - 1);
    }
    afis = putere(a, put - 1);
    printf("%d\n", afis);
    return 0;
}