划分哨兵

题目描述

相信你一定了解过快速排序这种基于随机化的高效排序算法，在算法中，我们将从当前序列中，随机选择一个位置的数作为哨兵，然后采用双指针的技巧，通过不断对哨兵左右两边的数进行交换，从而使得哨兵左边的数全部小于哨兵，而其右边的数全部大于哨兵。完成后，我们依次对哨兵左边和右边的部分再次重复上述过程，直到最后不存在哨兵以外的部分，则向上回溯，最后完成对整个序列的排序。

Orange在学习快速排序，他对其中哨兵的划分产生了非常强烈的兴趣，认为哨兵在对于排列的快速排序中具有某些重要性质。对于一个排列 $P$ 来说，Orange定义哨兵为排列中的某个特殊位置的值 $P_i$，在他前面的数全部小于它，在他后面的数全部大于他。形式化的说，$P_i$ 是哨兵，当且仅当 $\forall_{j i} \ P_j > P_i$。

对于一个 $n$-排列 $P$，Orange定义 $f(x)$ 表示 $x$ 作为排列中唯一的哨兵的不同排列的种类数量。你的任务是，帮助Orange求出每个 $f(x), \ (1 \le x \le n)$ 的值，答案可能很大，你只需要输出答案 $\bmod 10^9+7$ 即可。

$n$-排列指的是这样一个序列：对于一个长度为 $n$ 的序列，其中从 $1$ 开始到 $n$ 的每个数都不重不漏地出现了恰好一次。

输入格式

输入一行，为一个整数 $n$，表示排列长度。

数据范围

$1 \le n \le 5000$

输出格式

输出一行，包含 $n$ 个整数，其中第 $i$ 个数为 $f(i)$ 的值。

样例 #1

样例输入 #1

2

样例输出 #1

0 0

提示

样例解释

当 $n=3$ 时： 在所有 $1$ 是哨兵的 $3$-排列中，只有 $(1,3,2)$ 满足 $1$ 是唯一的哨兵，即 $f(1) = 1$。 在所有 $2$ 是哨兵的 $3$-排列中，不存在任何一种排列使得 $2$ 是唯一的哨兵，即 $f(2) = 0$。 在所有 $3$ 是哨兵的 $3$-排列中，只有 $(2,1,3)$ 满足 $3$ 是唯一的哨兵，即 $f(3) = 1$。 因此，答案为1 0 1。