#include <stdio.h>
#include <stdlib.h>

int ind_euler(int n) {
    int p, div=2, phi=1;
    while(div*div<=n) {
        p=1;
        while(n%div==0) {
            n/=div;
            p*=div;
        }
        if(p>1)
            phi*=((p/div)*(div-1));
        div++;
    }
    if(n>1)
        phi*=(n-1);
    return phi;
}

int rid_la_put(a, phi, n) {
    long long acc=1;
    while(phi>0) {
        if(phi%2)
            acc=(acc*a)%n;
        a=((long long)a*a)%n;
        phi/=2;
    }
    return acc;
}

int main()
{
    int a, n, phi;
    FILE *fi, *fo;
    fi = fopen("inversmodular.in", "r");
    fo = fopen("inversmodular.out", "w");
    fscanf(fi, "%d%d", &a, &n);
    phi=ind_euler(n);
    fprintf(fo, "%d", rid_la_put(a, phi-1, n));
    fclose(fi);
    fclose(fo);
    return 0;
}