#include "fstream"
#include "vector"
#include "cstring"

using namespace std;

ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");

const int NMAX = 10005;

long long A, N;
int prime[NMAX];

long long logPow(long long x, long long pow) {
    long long res = 1;
    while(pow) {
        if(pow % 2 == 1) {
            res = (res * x) % N;
            pow--;
        }
        if(!pow) {
            break;
        }
        x = (x * x)%N;
        pow /= 2;
//        fout << "Res: " << res << ", x: " << x << ", pow: " << pow << "\n";
    }
    return res;
}

int main() {

    fin >> A >> N;

    long long nCpy = N;
    long long coprimes = N;
    for(int i = 2 ; i * i <= N ; i++) {
        if(N % i == 0) {
            while(nCpy % i == 0) {
                nCpy /= i;
            }
            coprimes = coprimes - coprimes/i;
        }
    }
    if(nCpy > 1) {
        coprimes = coprimes - coprimes/nCpy;
    }

//    fout << "Coprimes: " << coprimes << "\n";

    fout << logPow(A, coprimes - 1);

    return 0;
}