#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using oset = tree<T, null_type, less<T>,
				  rb_tree_tag, tree_order_statistics_node_update>;

#ifdef Wi_TEST
	template<typename T1, typename T2>
	ostream& operator<<(ostream& out, pair<T1,T2> p) {
		out << "(" << p.first << ", " << p.second << ")";
		out.flush();
		return out;
	}
	#define deb(x) cout << #x << " = " << x << endl;
#else
	#define deb(x)
	#define cin fin
	#define cout fout
#endif

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

long long modpow(long long a, int p, long long mod) {
	if(p == 0) return 1;
	if(p & 1) return a * modpow(a*a%mod, p/2, mod) % mod;
	return modpow(a*a%mod, p/2, mod);
}

int main() {
	ios_base::sync_with_stdio(false);
	
	ifstream fin("inversmodular.in");
	ofstream fout("inversmodular.out");
	
	int a, n;
	cin >> a >> n;
	
	cout << modpow(a, phi(n)-1, n);
	return 0;
}