题目描述

对于一个 $1,\dots,n$ 的排列 $a_1,\dots,a_n$，定义 $i$ 处的顺序对数 $f(i)$ 为满足 $1\leq j \lt i$ 且 $a_j \lt a_i$ 的 $j$ 的数量，定义 $i$ 处的逆序对数 $g(i)$ 为满足 $i \lt j \leq n$ 且 $a_j \lt a_i$ 的 $j$ 的数量。

给定 $n$，对于每个 $k=0,1,\dots,n-1$，求出满足 $\max_{i=1}^n|f(i)-g(i)|=k$ 的 $a_1,\dots,a_n$ 的数量模 $10^9+7$ 的值。

输入格式

输入数据一行包含一个整数 $n$。

输出格式

输出一行 $n$ 个整数，分别表示 $k=0,1,\dots,n-1$ 时的答案，对 $10^9+7$ 取模。

样例

样例输入 1

2

样例输出 1

0 2

样例输入 2

5

样例输出 2

0 4 32 36 48

样例 3~4

见下发文件。

数据范围

• 对于前 $30\%$ 的数据，$n\leq 10$。
• 对于前 $60\%$ 的数据，$n\leq 5\times 10^3$。

对于 $100\%$ 的数据，$n\leq 10^6$。