#define ll long long
#define u64 unsigned long long
#define u128 __uint128_t
#define fo(i,x,y) for(int i = x;i <= y;++i)
namespace
{
	struct fastmod
	{
		int m;u64 b;
		void init(int p) {m = p,b = ((u128)(1) << 64) / m;}
		u64 operator ()(u64 a)
		{
			u64 q = (u128)(a) * b >> 64;
			u64 r = a - q * m;
			return r < m ? r : r - m;
		}
	}FM;
	int p,fac[2000010][7],pm[10],m,phi = 1,ans[7],mi[7][2000010],ifac[2000010];
	int mi2[1000010];
	int ksm(int x,ll y)
	{
		int res = 1;
		for(;y;y >>= 1,x = FM(1ll * x * x)) if(y & 1) res = FM(1ll * res * x);
		return res;
	}
	void inc(int &x,int y) {x = x + y >= p ? x + y - p : x + y;}
	void M(int *f,int x)
	{
		fo(i,1,m) while(x % pm[i] == 0) x /= pm[i],++f[i];
		f[0] = FM(1ll * f[0] * x);
	}
	int F[1000010];
	int C(ll N,ll M)
	{
		if(N < M || M < 0 || N < 0) return 0;
		if(N >= p || M >= p) return FM(1ll * C(N / p,M / p) * C(N % p,M % p));
		int res[7];
		fo(i,0,m) res[i] = FM(fac[N][i] * FM(1ll * ifac[M] * ifac[N - M]));
		fo(i,1,m) res[i] -= fac[M][i] + fac[N - M][i];
		int re = res[0];
		fo(i,1,m) re = FM(1ll * re * mi[i][res[i]]);
		return re;
	}
	int f(ll N,ll M)
	{
		if(M > N) M = N;
		if(M < 0) return 0;
		if(M == N) return mi2[FM(N)];
		if(N == 0) return M == 1;
		if(N <= p)
		{
			int res = 0;
			fo(i,0,M - 1) inc(res,C(N,i));
			return res;
		}
		return FM(1ll * mi2[2,FM(N)] * f(N / p,M / p) + 1ll * C(N / p,M / p) * f(FM(N),FM(M)));
	}
	int g(ll N,ll M)
	{
		if(M > N) M = N;
		if(M == N) return FM(FM(N) * mi2[FM(N - 1)]);
		if(N == 0) return 0;
		if(N <= p)
		{
			int res = 0;
			fo(i,0,M - 1) res = FM(res + 1ll * C(N,i) * i);
			return res;
		}
		return FM(FM(mi2[FM(N - 1)] * FM(N)) * f(N / p,M / p) + 1ll * C(N / p,M / p) * g(FM(N),FM(M)));
	}
}
void init(int o,int P)
{
	FM.init(p = P);
	for(int i = 2;i * i <= P;++i)
	{
		if(P % i == 0) P /= i,pm[++m] = i,phi *= i - 1;
		while(P % i == 0) P /= i,phi *= i;
	}
	if(P > 1) pm[++m] = P,phi *= P - 1;
	fac[0][0] = 1;
	fo(i,1,2000000)
	{
		fo(j,0,m) fac[i][j] = fac[i - 1][j];
		M(fac[i],i);
	}
	fo(i,0,2000000) ifac[i] = ksm(fac[i][0],phi - 1);
	fo(i,1,m)
	{
		mi[i][0] = 1;
		fo(j,1,2000000) mi[i][j] = FM(1ll * mi[i][j - 1] * pm[i]);
	}
	fo(i,1,1000000) F[i] = -1;
	mi2[0] = 1;
	fo(i,1,1000000) mi2[i] = FM(2 * mi2[i - 1]);
}
int ask(ll n)
{
	if(m == 1)
	{
		int iv = ksm(p + 1 >> 1,n << 1);
		int r1 = FM(FM(n) * (p + 1 - FM(1ll * iv * C(2 * n,n))));
		int r2 = FM(2ll * g(2 * n,n) * iv);
		return FM(r1 - r2 + p);
	}
	if(~F[n]) return F[n];
	int res = 0;
	fo(i,0,n - 1)
	{
		fo(j,0,m) ans[j] = fac[2 * n][j];
		ans[0] = FM(FM(1ll * ifac[i] * ifac[2 * n - i]) * ans[0]);
		fo(j,1,m) ans[j] -= fac[i][j] + fac[2 * n - i][j];
		int re = ans[0];
		fo(j,1,m) re = FM(1ll * re * mi[j][ans[j]]);
		res = FM(res + 1ll * re * (n - i));
	}
	return F[n] = FM(1ll * res * ksm(p + 1 >> 1,2 * n - 1));
}