#include<bits/stdc++.h>
// #define int long long
// #include "pilgrimage.h"
using namespace std;
int mo;
int nss,nsr;
int qpow(int x,int y){int ret=1;while(y){if(y&1)ret=1ll*ret*x%mo;y>>=1;x=1ll*x*x%mo;}return ret;}
void init(int o,int p)
{
    mo=p;
    nss=qpow(2,mo-2);
}
int ask(long long n)
{
    int cs=1;
    nsr=qpow(nss,n);
    int ret=1ll*nsr*cs*n%mo;
    for(int i=1;i<=n;++i)
    {
        cs=1ll*cs*(n-i+1)%mo;
        cs=1ll*cs*qpow(i,mo-2)%mo;
        ret=(ret+1ll*cs*nsr%mo*abs(n-i-i)%mo)%mo;
    }
    return ret;
}