#include<stdio.h>
#include<assert.h>

#include<algorithm>
#include<vector>

using namespace std;

int a, n, sol, mod;

void read(){
  assert(freopen("inversmodular.in", "r", stdin) != NULL);
  scanf("%d%d", &a, &n);
}

long long lg_put(int x,int pow){
  if(pow == 1)
    return x;
  return (lg_put(x,pow / 2) * lg_put(x,pow - pow / 2)) % mod;
}

void solve(){
  mod = n;
  sol = lg_put(a,n - 2);
}

void write(){
  assert(freopen("inversmodular.out", "w", stdout) != NULL);
  printf("%d",sol);
}

int main(){
  read();
  solve();
  write();
  return 0;
}