#include <bits/stdc++.h>
using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");
long long N, M, ans = 1, Phii;
long long Phi (long long A){
 long long ret = A;
 for (long long i = 2; i * i <= A; i ++){
  if (!(A % i)){
   while (A % i == 0)A /= i;
   ret = (ret / i) * (i - 1);
  }
 }
    if (A != 1)ret = ret / A * (A - 1);
 return ret;
}
int main (){
    fin >> N >> M;
    Phii = Phi (M) - 1;
    for (long long pw = 1; pw <= Phii; pw <<= 1){
   if (pw & Phii)ans = (ans * N) % M;
    N = (N * N) % M;
 }
 fout << ans;
 return 0;
}