公司网络中有 $$$n$$$ 台计算机。它们的编号从 $$$1$$$ 到 $$$n$$$。
对于每对两台计算机 $$$1 \leq i < j \leq n$$$,您知道值 $$$a_{i,j}$$$:在计算机 $$$i$$$ 和 $$$j$$$ 之间发送数据的难度。 $$$i<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} < a_{x,y}$$$。
对于每个 $$$1 \leq k \leq n$$$ 找到将计算机划分为 $$$k$$$ 组的方法数量,以便满足所有必需的条件。这些值可能很大,因此您需要通过对 $$$998\,244\,353$$$ 求模来找到它们。
输入
第一行包含一个整数 $$$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 < j \leq n$$$ $$$a_{i,j} > 0$$$;
- 对于所有 $$$1 \leq i < j \leq n$$$ $$$a_{i,j} = a_{j,i}$$$;
- $$$i <j$$$ 的所有 $$$a_{i,j}$$$ 都是不同的。
输出
打印 $$$n$$$ 整数:其中第 $$$k$$$ 应该等于将计算机划分为 $$$k$$$ 组的可能方法的数量,以便满足所有必需的条件,模 $$$998\,244\,353$$$。
示例
输入 #1
4 0 3 4 6 3 0 2 1 4 2 0 5 6 1 5 0
输出 #1
1 0 1 1
输入 #2
7 0 1 18 15 19 12 21 1 0 16 13 17 20 14 18 16 0 2 7 10 9 15 13 2 0 6 8 11 19 17 7 6 0 4 5 12 20 10 8 4 0 3 21 14 9 11 5 3 0
输出 #2
1 1 2 3 4 3 1
注意
以下是在第二个示例中将所有计算机分为 $$$4$$$ 组的所有可能方法:
- $$$\{1, 2\}, \{3, 4\}, \{5\}, \{6, 7\}$$$;
- $$$\{1\}, \{2\}, \{3, 4\}, \{5, 6, 7\}$$$;
- $$$\{1, 2\}, \{3\}, \{4\}, \{5, 6, 7\}$$$.