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

using namespace std;

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

const int NMAX = 10005;
const int MMAX = 10005;

int A, N;
int prime[NMAX];

int logPow(int x, int pow) {
    int res = 1;
    while(pow) {
        if(pow % 2 == 1) {
            res = (res * pow) % N;
            pow--;
        }
        if(!pow) {
            break;
        }
        x = (x * x)%N;
        pow /= 2;
    }
    return (x * res) % N;
}

int main() {

    fin >> A >> N;

    int nCpy = N;
    int 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;
}