#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
#define in f
#define out g
ifstream f ("inversmodular.in");
ofstream g ("inversmodular.out");

long long a, n;

long long pow(long long base, int exponent) {
    if (base == 0)
        return 0;
    if (base == 1)
        return 1;
    if (exponent == 0)
        return 1;
    if (exponent == 1)
        return base;
    else {
        if (exponent % 2 == 0)
            return pow(base * base, exponent / 2);
        else
            return base * pow(base * base, exponent / 2);
    }
}

int is_prime(long long n) {
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return 0;
    return 1;
}

long long coprime(long long x) {
    long long num = x;
    for (long long i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            while (x % i == 0)
                x /= i;
            num = (num / i) * (i - 1);
        }
    }
    if (x > 1)
        num = (num / x) * (x - 1);
    return num;
}

int main() {
    in >> a >> n;
    if (is_prime(n)) {
        long long k = pow(a, n - 2);
        out << k % n;
    } else {
        long long k = pow(a, coprime(n) - 1);
        out << k % n;
    }
}