#include <bits/stdc++.h>
#include "pilgrimage.h"
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
int P;
int ksm(ll x,int y){
	if(!x)return 1;
	ll u=ksm(x/2,y);
	u=u*u%P;
	if(x&1)u=u*y%P;
	return u;
}
int jc[1000011],ny[1000011];
void init (int o, int p)
{
	P=p;
	jc[0]=ny[0]=1;
	fo(i,1,p-1){
		jc[i]=(ll)jc[i-1]*i%p;
		ny[i]=ksm(p-2,jc[i]);
	}
	return;
}
int C(ll x,ll y){
	if(x<y)return 0;
	if(x<P)return (ll)jc[x]*ny[y]%P*ny[x-y]%P;
	return (ll)C(x/P,y/P)*C(x%P,y%P)%P;
}
int ask (long long n)
{
	ll u=(ll)(ksm(2*n,2)-C(2*n,n)+P)*ksm(P-2,2)%P;
	u=(u+C(2*n,n)-ksm(2*n-1,2)+P)%P;
	u=n%P*u%P;
	return u*ksm(P-2,ksm(n*2-1,2))%P;
}