#include <bits/stdc++.h>

using namespace std;

ifstream fin ("inversmodular.in");
ofstream fout ("inversmodular.out");

long long pw (long long a, long long b, long long mod){
   long long p = 1;
   while (b > 0){
      if (b & 1){
         p = (p * a) % mod;
      }
      a = (a * a) % mod;
      b >>= 1;
   }
   return p;
}

long long euler (long long a){
   long long ans = a, d = 2;
   while (a > 1){
      int p = 0;
      while (a % d == 0){
         a /= d;
         ++p;
      }
      if (p > 0){
         ans = ans * (d - 1) / d;
      }
      d += 1 + d % 2;
      if (d > a / d){
         d = a;
      }
   }
   return ans;
}


int main(){
   ios_base::sync_with_stdio(false);

   long long a, b; fin >> a >> b;
   fout << pw(a, euler(b) - 1, b);
}