#include <stdio.h>

int inv_modular(unsigned long long n) {
    unsigned long long rez = n;
    for (unsigned long long d = 2 ; d * d <= n; d++) {
            if (n % d == 0)
            {
                while(n % d == 0)
                {
                    n = n / d;
                    rez = rez - rez / d;
                }
            }
        }
    if(n > 1)
        rez = rez - rez / n;
    return rez;
}

long long exp_long(long long a, long long p, int n) {
    if (p == 0)
        return 1;
    long long rez = 1;
    a = a % n;
    while(p > 0)
    {
        if(p % 2 == 1)
            rez = (rez * a) % n;
        
        a = (a * a) % n;
        p = p / 2;
    }
    return rez;
}

int main(void)
{
    FILE *fin = NULL;
    FILE *fout = NULL;
    if((fin = fopen("inversmodular.in", "r")) == NULL) {
        fprintf(stderr, "Eroare la deschidere\n");
        return 1;
    }

    if((fout = fopen("inversmodular.out", "w")) == NULL) {
        fprintf(stderr, "Eroare la deschidere\n");
        fclose(fin);
        return 1;
    }

    int a, n;

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

    int p = inv_modular(n) - 1;
    long long rez = exp_long(a, p, n);
    fprintf(fout, "%lld\n", rez);


    fclose(fin);
    fclose(fout);



    return 0;
}