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

uint64_t n;

uint64_t eul(uint64_t n){
    uint64_t ans = n;
    uint64_t j = 2;
    if(n > 1){
        if(n % j == 0){
            ans = ans / j * (j - 1);
            while(n % j == 0){
                n /= j;
            }
        }
        ++j;
    }

    while(n > 1){
        if(n % j == 0){
            ans = ans / j * (j - 1);
            while(n % j == 0){
                n /= j;
            }
        }
        j += 2;
    }
    return ans;
}

int phiFunction(int n) {
    int result = n; // Initialize result as n

    // Find all prime factors of n
    for (int p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            // p is a prime factor of n
            while (n % p == 0) {
                n /= p;
            }
            // Reduce result using the formula: result = result * (1 - 1/p)
            result -= result / p;
        }
    }

    // If n has a prime factor greater than sqrt(n)
    if (n > 1) {
        result -= result / n;
    }

    return result;
}

uint64_t pw(uint64_t x,uint64_t e){
    uint64_t ans = 1, p = x;
    while(e){
        if(e & 1){
            ans = (ans * p) % n;
        }
        p = (p * p) % n;
        e >>= 1;
    }
    return ans;
}

int main(){
    freopen("inversmodular.in","r",stdin);
    freopen("inversmodular.out","w",stdout);
    uint64_t a;
    scanf("%llu %llu",&a,&n);
    printf("%llu",pw(a,eul(n) - 1));
    return 0;
}