#include<stdio.h>
#include<inttypes.h>

FILE *in, *out;

long long exp2(long long n, long long k, long long mod)
{
    if(k == 0) {
        return 1;
    }

    long long gay = exp2(n, k / 2, mod) % mod;
    if((k & 1) == 1) {
        return (((gay * gay) % mod) * n) % mod;
    } else {
        return (gay * gay) % 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++;
            toto = toto * i;
            trec = 1;
        }
        if(apa > 0) {
            toto = (toto * (i - 1)) / i;
        }
    }
    //printf("%dhuehue\n", toto);
    if(trec == 1) {
        return toto;
    } else {
        return n - 1;
    }
}

int main ()
{
    long long a, n;

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

    fscanf(in, "%lld%lld", &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;
}