题目描述

本题考虑从集合 $\{1,2,\ldots,n\}$ 映射到自身的函数。

对于函数 $f$，定义其 $k$ 次复合 $f^k(x)$：

• $f^0(x)=x$；
• 当 $k\ge1$ 时，$f^k(x)=f(f^{k-1}(x))$。

例如，当 $n=5$，且

$f(1)=4,f(2)=2,f(3)=2,f(4)=2,f(5)=1$，

则 $f^3$ 是恒等于 $2$ 的常值函数。

对于每个 $k=1,2,\ldots,n-1$，求有多少个函数 $f:\{1,\ldots,n\}\to\{1,\ldots,n\}$，使得 $f^k$ 为常值函数。

输入格式

输入一个整数 $n$，满足 $2\le n\le70$。

输出格式

输出 $n-1$ 个整数 $s_1,s_2,\ldots,s_{n-1}$。

其中 $s_k$ 表示满足 $f^k$ 为常值函数的函数数量，对 $10^9+7$ 取模后的结果。

样例输入

3

样例输出

3 9