话说这题一开始暴力判断的方式想错了导致乱想了半天……说明这种题还是先写暴力比较好……
因为表面是一个博弈，所以先考虑分析两方的最优策略。考虑分析一些性质。
Lemma：黑白棋子构成级极长同色连续段数量不会超过 。
证明显然，如果在某个时刻从 变成了 ，那么一定会将一段覆盖，变成 个极长同色连续段。
然后，对于这种覆盖的问题，一般都是有很多位置没有用，只用考虑一些特殊的位置。对于这题，由于是两个相同位置覆盖中间的，所以尝试着只考虑每种颜色最左/右出现的位置。
容易发现，令 为列表上位置 的颜色，若 ，那么最后全部一定都是 的棋子。证明显然。
否则不妨钦定 。此时我们只用关注最后一个 的位置 和最后一个 的位置 。若 则 ，答案为 。否则手玩发现，若先取到 再取到 ，那么黑方在取到 后可以直接取 ，因为 全黑，所以 不会再变成白色。同时 还没取，取到 后 全黑，也无法变成白色。所以最后黑棋数量为 。
那么策略就很显然了：黑方尽可能往 处靠，白方往 。直接对这个计数也是简单的：枚举起点 ，分成 以及一些特殊情况，分别预处理一些东西然后算。作者也是这么过的。
但是你会发现这太蠢了！除了 之外，的所有情况，如果将所有黑白翻转，答案就会变成 。若 且 也满足这个性质。此时期望就是 。但是若 ，黑方由于先手，所以一定能抢先取到 。于是期望要加上 。只用简单预处理，统计所有这样的贡献之和即可。
code：
int n,m,f[N];
il int Mod(int x,int y){
return x+y>=mod?x+y-mod:x+y;
}
il int qpow(int x,int y){
int ret=1;
while(y){
if(y&1){
ret=1ll*ret*x%mod;
}
x=1ll*x*x%mod,y>>=1;
}
return ret;
}
void Yorushika(){
read(n);
int pw=2;
rep(i,1,n){
f[i]=Mod(f[i-1],1ll*pw*(i+i+1)%mod);
pw=4ll*pw%mod;
}
const int iv=qpow(qpow(2,n),mod-2);
rep(i,1,n){
int ans=1ll*n*((mod+1)/2)%mod;
if(n>=4&&i>2&&i<n-1){
ans=Mod(ans,1ll*f[min(i-2,n-1-i)]*iv%mod);
}
printf("%d\n",ans);
}
}
signed main(){
int t=1;
//read(t);
while(t--){
Yorushika();
}
}
