CF1408G.Clusterization Counting

There are $n$ computers in the company network. They are numbered from $1$ to $n$.

For each pair of two computers $1 \leq i \lt j \leq n$ you know the value $a_{i,j}$: the difficulty of sending data between computers $i$ and $j$. All values $a_{i,j}$ for $i \lt j$ are different.

You want to separate all computers into $k$ sets $A_1, A_2, \ldots, A_k$, such that the following conditions are satisfied:

• for each computer $1 \leq i \leq n$ there is exactly one set $A_j$, such that $i \in A_j$;
• for each two pairs of computers $(s, f)$ and $(x, y)$ ($s \neq f$, $x \neq y$), such that $s$, $f$, $x$ are from the same set but $x$ and $y$ are from different sets, $a_{s,f} \lt a_{x,y}$.

For each $1 \leq k \leq n$ find the number of ways to divide computers into $k$ groups, such that all required conditions are satisfied. These values can be large, so you need to find them by modulo $998\,244\,353$.

公司网络中有 $n$ 台计算机，编号为 $1$ 到 $n$。

对于每一对满足 $1 \leq i \lt j \leq n$ 的计算机，已知一个值 $a_{i,j}$：表示在计算机 $i$ 与 $j$ 之间传输数据的难度。所有满足 $i \lt j$ 的 $a_{i,j}$ 值互不相同。

你需要将全部计算机划分为 $k$ 个集合 $A_1, A_2, \ldots, A_k$，使得以下条件成立：

• 对于每台计算机 $1 \leq i \leq n$，恰好存在一个集合 $A_j$，使得 $i \in A_j$；
• 对于任意两对计算机 $(s, f)$ 和 $(x, y)$（其中 $s \neq f$，$x \neq y$），若 $s$、$f$、$x$ 属于同一集合，而 $x$ 与 $y$ 属于不同集合，则必有 $a_{s,f} \lt a_{x,y}$。

对每个 $1 \leq k \leq n$，求出将计算机划分为 $k$ 个组、且满足上述所有条件的方案数。答案可能很大，因此需对 $998\,244\,353$ 取模。

The first line contains a single integer $n$ ($1 \leq n \leq 1500$): the number of computers.

The $i$-th of the next $n$ lines contains $n$ integers $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$($0 \leq a_{i,j} \leq \frac{n (n-1)}{2}$).

It is guaranteed that:

• for all $1 \leq i \leq n$ $a_{i,i} = 0$;
• for all $1 \leq i \lt j \leq n$ $a_{i,j} \gt 0$;
• for all $1 \leq i \lt j \leq n$ $a_{i,j} = a_{j,i}$;
• all $a_{i,j}$ for $i \lt j$ are different.

第一行包含一个整数 $n$（$1 \leq n \leq 1500$）：计算机的数量。

接下来的 $n$ 行中，第 $i$ 行包含 $n$ 个整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$（$0 \leq a_{i,j} \leq \frac{n (n-1)}{2}$）。

保证满足以下条件：

• 对所有 $1 \leq i \leq n$，有 $a_{i,i} = 0$；
• 对所有 $1 \leq i \lt j \leq n$，有 $a_{i,j} \gt 0$；
• 对所有 $1 \leq i \lt j \leq n$，有 $a_{i,j} = a_{j,i}$；
• 所有满足 $i \lt j$ 的 $a_{i,j}$ 互不相同。

Print $n$ integers: the $k$-th of them should be equal to the number of possible ways to divide computers into $k$ groups, such that all required conditions are satisfied, modulo $998\,244\,353$.

输出 $n$ 个整数：其中第 $k$ 个整数应等于将计算机划分为 $k$ 个组的方案数（需满足所有给定条件），并对 $998\,244\,353$ 取模。

Here are all possible ways to separate all computers into $4$ groups in the second example:

• ${1, 2}, {3, 4}, {5}, {6, 7}$;
• ${1}, {2}, {3, 4}, {5, 6, 7}$;
• ${1, 2}, {3}, {4}, {5, 6, 7}$.

第二个示例中，将所有计算机划分为 $4$ 组的所有可能方式如下：

• ${1, 2}, {3, 4}, {5}, {6, 7}$；
• ${1}, {2}, {3, 4}, {5, 6, 7}$；
• ${1, 2}, {3}, {4}, {5, 6, 7}$。