#include <fstream>

using namespace std;

bool estePrim(const int n) {
    if(n < 2)
        return false;

    for(int i = 2; i * i <= n; i++)
        if(n % i == 0)
            return false;
    return true;
}


long long fi(int n) {
    if(n == 0)
        return 0;

    if(estePrim(n))
        return n - 1;

    long long factor = n, numarator = 1;

    for(long long i = 2; i * i <= n; i++)
        if(n % i == 0) {
            factor /= i;
            numarator *= i - 1;

            while(n % i == 0)
                n /= i;
        }

    if(n != 1) {
        factor /= n;
        numarator *= n - 1;
    }

    return factor * numarator;
}

long long ridica(long long a, long long b, int n){
    long long result = 1;

    while (b) {
        if (b % 2 == 1){
            result = result * a % n;
        }
        b /= 2;
        a = a * a % n;
    }

    return result;
}

int main() {
    ifstream in("inversmodular.in");
    ofstream out("inversmodular.out");

    int a, n;
    in >> a >> n;
    out << ridica(a, fi(n) - 1, n);

    return 0;
}