/* inversul modular */

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

long long m;  // Valoarea modulului

// Funcția phi Euler pentru a calcula numărul de numere întregi pozitive
//mai mici sau egale cu n și prime față de n
long long phi(long long n) {
	int i;
	long long rezultat = n;
	for (i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			while (n % i == 0)
				n = n / i;
			rezultat = rezultat - rezultat / i;
		}
	}
	if (n > 1)
		rezultat = rezultat - rezultat / n;
	return rezultat;
}

// Funcția pentru exponențierea în modul eficient
long long putere(long long a, long long n) {
	long long rezultat = 1;
	while (n > 0) {
		if (n % 2 == 1)
			rezultat = (rezultat * a) % m;
		a = (a * a) % m;
		n = n / 2;
	}
	return rezultat;
}

int main() {
	FILE *fin, *fout;
	long long a, n;
	fin = fopen("inversmodular.in", "r");  // Deschiderea fișierului de intrare
	fout = fopen("inversmodular.out", "w");  // Deschiderea fișierului de ieșire
	fscanf(fin, "%lld %lld", &a, &n);  // Citirea valorilor a și n din fișierul de intrare
	m = n;  // Stabilirea valorii modulului
	fprintf(fout, "%lld", putere(a, phi(n) - 1));  // Calculul inversului modular și scrierea rezultatului în fișierul de ieșire
	fclose(fin);  
	fclose(fout);  
	getchar();  
	return 0;
}