#include<bits/stdc++.h>
using namespace std;
int main()
{
  unsigned long long N; cin >> N;
  unsigned int B; cin >> B;
  unsigned int euler = B;
  unsigned int B_copy = B;
  for( unsigned int i = 2 ; i * i <= B_copy ; i++ ){
    if( B_copy % i == 0 ){
      euler /= i;
      euler *= i - 1;
      B_copy /= i;
      while( B_copy % i == 0 ){
	B_copy /= i;
      }
    }
  }
  if( B_copy != 1 ){
    euler /= B_copy;
    euler *= B_copy - 1;
  }
  N %= B;
  unsigned int exponent = euler - 1;
  unsigned long long power_N = 1 % B;
  unsigned long long power_power_N = N;
  while( exponent > 0 ){
    if( exponent % 2 == 1 ){
      power_N *= power_power_N;
      power_N %= B;
    }
    power_power_N *= power_power_N;
    power_power_N %= B;
    exponent /= 2;
  }
  if( power_N * N % B == 1 % B ){
    cout << power_N << "\n";
  } else {
    cout << "NaN\n";
  }
}