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

#include<algorithm>
#include<vector>

using namespace std;

int a, n, sol, mod, ix;

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;
  x = lg_put(x,pow / 2);
  if(pow % 2 == 0)
    return ((long long)x * x) % mod;
  else
    return ((((long long)x * x) % mod )* ix) % mod;
}

void solve(){
  mod = n;
  ix = a;
  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;
}