题目描述

函数图是一张每个结点出度都为 $1$ 的有向图。

给定 $n$，对每个 $k=1,2,\ldots,n$，请计算有多少个 $n$ 个结点的函数图恰好有 $k$ 个连通分量。

输入格式

输入一行一个整数 $n$，表示结点数。

输出格式

输出 $n$ 行，第 $k$ 行表示恰好有 $k$ 个连通分量的函数图数量，对 $10^9+7$ 取模。

数据范围

• $1 \le n \le 5000$

样例

样例输入

3

样例输出

17
9
1