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

#define INPUT_FILE "inversmodular.in"
#define OUTPUT_FILE "inversmodular.out"

long long phi(long long n) {
    long long current = n;
    for(long long i=2;i*i<=n;i++) {
        if(n % i == 0) {
            while(n % i == 0) n /= i;
            current = (current / i) * (i - 1);
        }
    }
    if(n != 1) {
        current = current / n * (n - 1);
    }
    return current;
}

int main() {
    long long a = 0, n = 0;
    FILE *in = NULL, *out = NULL;
    
    if((in = fopen(INPUT_FILE, "r")) == NULL) {
        fprintf(stderr, "Eroare la deschidere fisier intrare\n");
        exit(-1);
    }

    if((out = fopen(OUTPUT_FILE, "w")) == NULL) {
        fprintf(stderr, "Eroare la deschidere fisier iesire\n");
        exit(-1);
    }

    fscanf(in, "%lld %lld", &a, &n);
    long long p = phi(n) - 1;
    long long number = 1;
    long long newA = a;
    for(long long i=1;i<=p;i<<=1) {
        if(i & p) {
            number = (number * newA) % n;
        }
        newA = (newA * newA) % n;
    }

    fprintf(out, "%lld\n", number);

    fclose(in);
    fclose(out);
    return 0;
}