Problem Description

Build a directed graph $G$ with $N$ vertices, with no edges at the beginning.

Next, build an edge sequence $A$ of length $E$. Each edge in the sequence is a directed edge $(s,t)$ satisfying $1 \le s,t \le N$ and $s \ne t$, and all edges in the sequence are distinct.

Add these edges to $G$ in order. After each addition, compute and record the current number of strongly connected components in the graph, obtaining a new positive integer sequence $B$ of length $E$.

• If two edge sequences produce the same $B$, then they are called essentially the same.

How many essentially different edge sequences are there? You only need to output the answer modulo $10^9+7$.

Input Format

Input one line containing a positive integer $N$, which denotes the number of vertices in the directed graph $G$.

Output Format

Output one line containing $N \times (N-1)$ integers separated by spaces. The $i$-th number represents the answer when $E=i$.

3

1 2 4 7 7 7

Hint

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): No special constraints.

Constraints: For all data, $N \le 400$.

For the first $6$ subtasks, the time limit is $1\text s$, and for the $7$-th it is $3.5\text s$.

Code length limit: 10kb. If it exceeds this limit, it will be marked as invalid after the contest.

Translated by ChatGPT 5