#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define INFI 999999
#define int long long

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

#define cin in
#define cout out

const int N = 1e3 + 1;

int p , MOD;

int phi(int n)
{
	int r = n;
	for (int i = 2; i * i <= n; i++) // nu merge pana la copie de n
	{
		if (n % i == 0)
		{
			r -= r / i;
			while (n % i == 0)
			{
				n /= i;
			}
		}
	}
	if (n != 1)
		r -= r / n; // de ce?
	return r;
}

int fast_expo(int nr, int putere)
{
	if (putere == 0)
		return 1;
	if (putere == 1)
		return nr;
	if (putere % 2 == 0)
	{
		int x = fast_expo(nr, putere / 2) % MOD;
		return (x * x) % MOD;
	}
	else
	{
		int x = fast_expo(nr, putere - 1) % MOD;
		return (nr * x) % p;
	}
}

signed main()
{
	int a;
	cin >> a >> p;
	MOD = p;
	int putere = phi(p) - 1;
	int rez = fast_expo(a, putere);
	cout << rez;
}