#include <bits/stdc++.h>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

long long N;
int P;

long long lgput(long long N, int P, const int MOD){
	long long res = 1;
	while(P){

		if(P & 1) res = (res * N) % MOD;
		N = (N * N) % MOD;
		P >>= 1LL;
	}
	return res;
}

int Phi(int n){
    int d, nr = n;
    for (d = 2; n > 1 && d * d <= n; d++){
        if (n % d == 0){
            nr = nr / d * (d - 1);
            while (n % d == 0) {n /= d;}
        }
    }
    if (n > 1) {nr = nr / n * (n - 1);}
    return nr;
}

int main(){

	f >> N >> P;
	g << lgput(N, Phi(P) - 1, P);
}