#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define _1 first
#define _2 second
const int N = 1000010, L = 50;
int p, phi;
int cnt;
pair <int, int> vec[L];
int fac[L][N];
int exgcd(int a, int b, int & x, int & y) {
	if (!b) {
		x = 1;
		y = 0;
		return a;
	}
	ll d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int inv(int a, int b) {
	int x, y, d = exgcd(a, b, x, y);
	int t = b / d;
	x = (x % t + t) % t;
	return x;
}
int quick_pow(int x, int y, int p) {
	int res = 1;
	for (; y; y >>= 1, x = (ll) x * x % p)
		if (y & 1) res = (ll) res * x % p;
	return res;
}
int calc(ll n, int k) {
	int x = vec[k]._1;
	int p = vec[k]._2;
	int phi = p / x * (x - 1);
	return n ? (ll) quick_pow(fac[k][p], n / p % phi + phi, p) * fac[k][n % p] % p * calc(n / x, k) % p : 1;
}
int solve(ll n, int k) {
	ll cnt = 0;
	int x = vec[k]._1;
	int p = vec[k]._2;
	int phi = p / x * (x - 1);
	for (ll i = n << 1; i; i /= x) cnt += i / x;
	for (ll i = n; i; i /= x) cnt -= i / x * 2;
	int t = calc(n, k);
	return (ll) quick_pow(x, cnt % phi + phi, p) * calc(n << 1, k) % p * inv((ll) t * t % p, p) % p;
}
void init(int o, int p0) {
	p = p0;
	phi = p;
	cnt = 0;
	for (int i = 2; i * i <= p0; ++i) {
		if (p0 % i) continue;
		int d = 1;
		while (!(p0 % i)) {
			p0 /= i;
			d *= i;
		}
		vec[cnt++] = {i, d};
		phi = phi / i * (i - 1);
	}
	if (p0 > 1) {
		vec[cnt++] = {p0, p0};
		phi = phi / p0 * (p0 - 1);
	}
	for (int i = 0; i < cnt; ++i) {
		fac[i][0] = 1;
		for (int j = 1; j <= vec[i]._2; ++j)
			fac[i][j] = (ll) fac[i][j - 1] * (j % vec[i]._1 ? j : 1) % vec[i]._2;
	}
}
int Lucas(ll n) {
	int res = 0;
	for (int i = 0; i < cnt; ++i)
		res = (res + (ll) solve(n, i) * (p / vec[i]._2) % p * inv(p / vec[i]._2 % vec[i]._2, vec[i]._2) % p) % p;
	return res;
}
int ask(ll n) {
	return (ll) inv(quick_pow(4, n % phi + phi, p), p) * (n % p) % p * Lucas(n) % p;
}