#include <cstdio>
#include <cmath>
using namespace std;
int MOD;
int mypow(int a, int b){
  int ans = 1;
  for (; b; b >>= 1){
    if (b & 1)
      ans = (1LL * ans * a) % MOD;
    a = (1LL * a * a) % MOD;
  }
  return ans;
}
int main(){
  freopen("inversmodular.in", "r", stdin);
  freopen("inversmodular.out", "w", stdout);
  int n, a, ans, i, phi;
  scanf("%d%d", &a, &n);
  phi = MOD = n;
  for (i = 2; 1LL * i * i <= n; i ++)
    if (n % i == 0){
      while (n % i == 0)
        n /= i;
      phi = phi / i * (i - 1);
    }
  if (n > 1)
    phi = phi / n * (n - 1);
  ans = mypow(a, phi - 1);
  printf("%d\n", ans);
  return 0;
}