#include <bits/stdc++.h>

using namespace std;

ifstream f("inversmodular.in");
ofstream g("inversmodular.out");

int log_exp(int x, int n, int N){
    
    x = x % N;
    
    if(n == 0) return 1;
    
    int p = 1;
    
    while(n > 0){
      if(n%2){
        p = (p * x) % N;
      }
    x = (x * x) % N;
    n = n /2;
 }
 
 return p % N;
   
}

int phi(int n) {
 int result = n;
 for (int i = 2; i * i <= n; i++) {
 if (n % i == 0) {
 while (n % i == 0)
 n /= i;
 result -= result / i;
 }
 }
 if (n > 1)
 result -= result / n;
 return result;
}


int main(void){
    
    int a, n;
    
    f >> a >> n;
    
    g << log_exp(a,phi(n)-1,n);
    
    return 0;
}