/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <fstream>
using namespace std;

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


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;
}

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

int main()
{
    
	int a, n;
	fin>>a>>n;
	fout<<exp_log(a,phi(n)-1,n);

	return 0;
}