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 < 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

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 < j \leq n $ $ a_{i,j} > 0 $ ; - for all $ 1 \leq i < j \leq n $ $ a_{i,j} = a_{j,i} $ ; - all $ a_{i,j} $ for $ i

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 $ .

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\} $ .