#include <stdio.h>

int inv_modular(unsigned long long n) {
    unsigned long long rez = n;
    for (unsigned long long d = 2 ; d < n * 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;
}

unsigned long long exp_long(unsigned long long a, unsigned long long p, unsigned long long n) {
    unsigned 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;
    }

    unsigned long long a, n;

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

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


    fclose(fin);
    fclose(fout);



    return 0;
}