#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll fExp(ll a, ll b, ll m){
	ll ans = 1;
	while(b){
		if(b & 1){
			ans = ans * a % m;
		}
		a = a*a % m;
		b >>= 1;
	}
	return ans;
}

ll phi(int a){
	ll ans = a;
	for(int i = 2; i * i <= a; ++i){
		if(a % i == 0){
			while(a % i == 0)
				a /= i;
			ans -= ans/i;
		}
	}
	if(a > 1) ans -= ans / a;
	return ans;
}

// n^e mod m = n^phi(m) * n^(e mod phi(m)) mod m
ll expo(ll n, ll m){
	if(m == 1) return 0;
	if(n == 1){
		return 1 % m;
	}
	if(n == 2){
		return 2 % m;
	}
	if(n == 3){
		return 9 % m;
	}
	if(n == 4){
		return 262144 % m;
	}
	ll p =  phi(m);
	ll f = fExp(n, p, m);
	ll s = fExp(n, expo(n - 1, p), m);
	return (f * s) % m;
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m;
	cout << expo(n, m) << '\n';

	return 0;
}