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


int cmmdc(int x, int y){
    int z = x % y;
    while (z != 0){
        x = y;
        y = z;
        z = x % y;
    }
    return y;
}

int prim(int n){
    int p=1;
    for (int i=2; i<n; i++){
        if (cmmdc(n, i) == 1)
            p++;
    }
    return p;
}

long long modmult(long long x, long long y, long long mdl){
    return ((x % mdl) * (y % mdl)) % mdl;
}

int putere(int a, int exp, int N){ // (a^exp)%n
    int m = 1;
    long long ai = a, afin = 1;

    for (int i=0; i<32; i++)
    {
        if (exp & m)
            afin = modmult(ai, afin, N);

        ai = modmult(ai, ai, N);
        m <<= 1;
    }

    return afin;
}

int main()
{
    freopen("inversmodular.in", "r", stdin);
    freopen("inversmodular.out", "w", stdout);

    int a, n;
    scanf("%d %d", &a, &n);

    printf("%d", putere(a, prim(n)-1, n));
}