链接: https://cses.fi/problemset/task/2415

板块: Counting Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

函数图是一种有向图，其中每个节点的出度均为 $1$。例如，下面是一个有 $9$ 个节点、$2$ 个连通分量的函数图：示意图 https://cses.fi/file/39a5e727e368197cdce7593736c5cfd1abf75b6439c0823e27c671ff10662377

给定 $n$，你的任务是计算对于每个 $k=1 \dots n$，具有 $n$ 个节点和 $k$ 个连通分量的函数图的数量。

输入

唯一的一行输入包含一个整数 $n$：节点数量。

输出

输出 $n$ 行：对于每个 $k=1 \dots n$，输出图的数量，对 $10^9+7$ 取模。

数据范围

$1 \le n \le 5000$

样例输入

3

样例输出

17
9
1