#include<stdio.h>

FILE *in, *out;

int exp(long long int n, long long int k)
{
    if(k == 0) {
        return 1;
    }
    if((k & 1) == 1) {
        return (((exp(n, k / 2) * exp(n, k / 2))) * n);
    } else {
        return (exp(n, k / 2) * exp(n, k / 2));
    }
}

long long int exp2(long long int n, long long int k, int mod)
{
    if(k == 0) {
        return 1;
    }
    if((k & 1) == 1) {
        return (((exp2(n, k / 2, mod) * exp2(n, k / 2, mod)) % mod) * n) % mod;
    } else {
        return (exp2(n, k / 2, mod) * exp2(n, k / 2, mod)) % mod;
    }
}

int fi(int n)
{
    int apa, cn = n, toto = 1;
    int trec = 0;

    for(int i = 2; i * i <= n; i++) {
        apa = 0;
        while(cn % i == 0) {
            cn = cn / i;
            apa++;
        }
        if(apa > 0) {
            toto = toto * exp(i, apa - 1) * (i - 1);
            trec = 1;
        }
    }
    //printf("%dhuehue\n", toto);
    if(trec == 1) {
        return toto;
    } else {
        return n - 1;
    }
}

int main ()
{
    int a, n;

    in = fopen("inversmodular.in", "r");
    out = fopen("inversmodular.out", "w");

    fscanf(in, "%d%d", &a, &n);

    int x = fi(n);
    //printf("uhauhauahuha %d\n", x);
    long long y = exp2(a, x - 1, n);
    fprintf(out, "%lld", y);

    fclose(in);
    fclose(out);

    return 0;
}