题目描述

构建一个 $N$ 个点的有向图 $G$，初始没有任何边。

接下来构建一个长度为 $E$ 的边的序列 $A$，序列中每条边都是满足 $1\le s,t\le N$ 且 $s\neq t$ 的有向边 $(s,t)$，且序列中的边互不相同。

按照顺序把这些边加入到 $G$ 中，每次加入后计算当前图的强连通分量个数并记录下来，得到一个新的长度为 $E$ 的正整数序列 $B$。

• 如果两个边的序列得到的 $B$ 相同则称它们 本质相同。

请问有多少种本质不同的边的序列，你只要求出答案对 $10^9+7$ 取模后的结果。

输入格式

输入一行，一个正整数 $N$ 表示有向图 $G$ 的点数。

输出格式

输出一行 $N\times(N-1)$ 个由空格隔开的整数，第 $i$ 个数表示当 $E=i$ 时的答案。

3

1 2 4 7 7 7

提示

Subtask 1 (5pts)：$N\le 5$。

Subtask 2 (10pts)：$N\le 10$。

Subtask 3 (15pts)：$N\le 20$。

Subtask 4 (15pts)：$N\le 30$。

Subtask 5 (15pts)：$N\le 50$。

Subtask 6 (20pts)：$N\le 100$。

Subtask 7 (20pts)：无特殊限制。

对于全部数据：$N\le 400$。

前 $6$ 个子任务限时 $1\text s$，第 $7$ 个 $3.5\text s$。

代码长度限制：10kb 超过这个限制赛后将会被标记为无效。