#include <iostream>
#include <vector>
#include <map>
#include <math.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <time.h>
using namespace std;
#define inf 0x3f3f3f3f
#define minf 0x3f
#define inp(x) cin>>x
#define otp(x) cout<<x
#define otp_nl(x) cout<<x<<"\n"
#define otp_sp(x) cout<<x<<" "
#define int long long
#define veci vector<int>
#define str string
#define pb(x) push_back(x)
#define fr(k,len) for(k=0;k<len;k++)
#define nfr(k,len) for(int k=0;k<len;k++)
#define ret return
#define db long double
#define all(x) x.begin(),x.end()

namespace my_stl {

}

inline int read(int mod) {
	int x = 0;
	char ch = getchar();
	while (!isdigit(ch))
		ch = getchar();
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - 48;
		x %= mod;
		ch = getchar();
	}
	return x;
}

int qpow(int a, int t, int p) {
	a %= p;
	int b[64];
	b[0] = a;
	nfr(i, 63)b[i + 1] = (b[i] * b[i]) % p;
	int ans = 1;
	nfr(i, 64) {
		if (t & (1ll << i)) {
			ans *= b[i];
			ans %= p;
		}
	}
	ret ans;
}

int gcd(int a, int b) {
	ret (b ? (gcd(b, a % b)) : a);
}

int invp(int a, int p) {
	ret qpow(a, p - 2, p);
}
int x, y;

void exgcd(int a, int b, bool f) {
	if (f)
		x = 0, y = 0;
	if (!b) {
		x = 1;
		y = 0;
		return;
	}
	exgcd(b, a % b, false);
	int tx = x;
	x = y;
	y = tx - a / b * y;
}

int inv(int a, int p) {
	exgcd(a, p, true);
	return (x + p) % p;
}

void solve() {
	int a, m, b;
	cin >> a >> m;
	int phim = m;
	for (int i = 2; i * i <= m; i++) {
		if (m % i == 0) {
			phim /= i;
			phim *= (i - 1);
			while (m % i == 0) {
				m /= i;
			}
		}
	}
	if (m != 1) {
		phim /= m;
		phim *= (m - 1);
	}
	b = read(phim);
	if (b >= phim)
		b += phim;
	int ans = 1;
	for (int i = 0; i < b; i++) {
		ans *= a;
		ans %= m;
	}
	cout << ans;
	ret;
}

signed main() {
	int t = 1;
	nfr(i, t) {
		solve();
	}
	ret 0;
}

样例2输出395