#include <bits/stdc++.h>
using namespace std;
ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");
int a, n;
int euler (int n) {
  int d = 2, rez = n, e;
  while (d * d <= n && n > 1) {
    e = 0;
    while (n % d == 0) {
      e++;
      n /= d;
    }
    if (e > 0)
      rez = rez / d * (d - 1);
    d++;
  }
  if (n > 1)
    rez = rez / n * (n - 1);
  return rez;
}
int  modulo(int a, int b) {
  if (b == 0)
    return 1;
    else {
  long long x = modulo(a, b / 2);
    if (b % 2 == 0)
      return x * x % n;
    else
      return x * x % n * a % n;
    }
}
int main()
{
    fin >> a >> n;
    int p = euler(n) - 1;
    fout << modulo(a, p);
    return 0;
}