题目背景

你对 $\text{min}\times \text{mex}$ 问题颇有研究！

题目描述

小 A 给你了一个数字 $n$，要求你求解 $\text{mex}$ 问题！你当然对 $\text{min}\times \text{mex}$ 问题颇有研究，决定来秒掉这道题！

定义集合 $S(A)$，$A$ 是一个序列，当且仅当以数字 $x$ 作为最小值的 $A$ 的子区间的个数为奇数时，$x$ 属于集合 $S(A)$。你需要对于每一个 $i=0,1,2,\dots,n$ 分别求出 $\text{mex}\{S(a)\}=i$ 的序列 $a$ 的数量，其中序列 $a$ 是 $0$ 到 $n-1$ 的任意一个排列。

答案可能较大，请对 $10^9+7$ 取模。

$\text{mex}$ 函数定义：设 $S$ 是一个非负整数集合，则 $\text{mex}(S)$ 定义为不在集合 $S$ 中的最小非负整数。用数学符号表示为：$\operatorname{mex}(S)=\min\{x\in\mathbb{N}:x\notin S\}$。

输入格式

输入一行整数 $n$，代表排列数组 $a$ 的长度。

输出格式

输出 $n+1$ 行，每行一个整数，意义如题面所述。

2

2
0
0

提示

【样例解释 $\mathbf 1$】

可以得到，$S([1,0])=S([0,1])=\{1\}$。

• 当 $i=0$ 时，$\text{mex}\{S(a)\}=0$ 的序列 $a$ 有两种，分别是 $[0,1]$ 和 $[1,0]$。
• 当 $i=1$ 时，$\text{mex}\{S(a)\}=1$ 的序列 $a$ 不存在。
• 当 $i=2$ 时，$\text{mex}\{S(a)\}=2$ 的序列 $a$ 不存在。

【数据规模与约定】

本题开启子任务捆绑测试。本题自动开启 O2 优化。请注意使用较快的输出方式。

• Subtask 1（30 pts）：$n\leq 10$。
• Subtask 2（20 pts）：$n\leq 100$。
• Subtask 3（20 pts）：$n\leq 1000$。
• Subtask 4（30 pts）：$n\leq 5\times 10^6$。

对于所有测试点满足 $1\leq n\leq 5\times 10^6$。