P11742 Dynamic Mex Problem

你对 $\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\}$。

无

无

**【样例解释 $\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$。