#include <fstream>

using namespace std;

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

int a, n;

int exp(int N, int p) {
	int r = 1;
	while (p) {
		if (p % 2 == 1)r = (1LL * N * r) % n;
		N =(1LL * N * N) % n;
		p /= 2;
	}
	return r;
}

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

int main() {
	ios_base::sync_with_stdio(false);
	in.tie(NULL), out.tie(NULL);
	in >> a >> n;
	out << exp(a, phi(n) - 1) % n;
	
}