Description

Looking at so many clothes covered with dust, the two of them felt helpless. Also, some clothes cannot be washed together. To sort them into categories, Xiaokeke gave each piece of clothing a distinct label from $1 \sim n$, where $n$ is the number of clothes. It would be more convenient to wash them after arranging the clothes in the order $1,2,\ldots,n$.

Xiaokeke also thought that we can take out a continuous segment of the clothes rack, reverse its order by hand, and then put it back. As an OI contestant, you immediately abstracted Xiaokeke’s algorithm for sorting clothes: let the label of the $i$-th piece of clothing from left to right initially be $p_i$. Enumerate $i$ in the order $1,2,\ldots,n-1$. Let the smallest label among $p_i,p_{i+1},\ldots,p_n$ be $p_j$. Then reverse $p_i,p_{i+1},\ldots,p_{j-1},p_j$ from left to right, turning it into $p_j,p_{j-1},\ldots,p_{i+1},p_i$.

Xiaoxue soon discovered that although Xiaokeke’s algorithm looks impressive, it is actually quite silly—in the dim light, nobody can tell the labels on the clothes. So they could only return to the room for rational enjoyment: assume the cost of reversing the interval $[i,j]$ is $w_{i,j}$. The cost of one sorting process is the sum of the operation costs of all reversals. Now Xiaokeke wants to know, when $p$ ranges over all $n!$ permutations, the total sorting cost over all cases.

You only need to output the answer modulo $998244353$ ($=7 \times 17 \times 2^{23} + 1$, a prime).

Input Format

The first line contains an integer $n$.

The next $n-1$ lines: in line $i$ $(1 \le i \le n)$, there are $n - i + 1$ space-separated integers, where the $j$-th one denotes $w_{i,j}$.

Output Format

One line containing an integer, which is the answer modulo $998244353$.

5
1 2 3 4 5
1 2 3 4
1 2 3
1 2

1080

见附加文件的 sort2.in。 

见附加文件的 sort2.ans。

Hint

[Sample 1 Explanation]

Let us give an example. When $p=[3,2,5,1,4]$, the steps of the algorithm are as follows:

• When executing $i=1$, the minimum among $p_1,p_2,p_3,p_4,p_5$, i.e. $3,2,5,1,4$, is $p_4=1$. We reverse interval $[1,4]$, and $p$ becomes $[1,5,2,3,4]$, with cost $w_{1,4}=4$.
• When executing $i=2$, the minimum among $p_2,p_3,p_4,p_5$, i.e. $5,2,3,4$, is $p_3=2$. We reverse interval $[2,3]$, and $p$ becomes $[1,2,5,3,4]$, with cost $w_{2,3}=2$.
• When executing $i=3$, the minimum among $p_3,p_4,p_5$, i.e. $5,3,4$, is $p_4=3$. We reverse interval $[3,4]$, and $p$ becomes $[1,2,3,5,4]$, with cost $w_{3,4}=2$.
• When executing $i=4$, the minimum among $p_4,p_5$, i.e. $5,4$, is $p_5=4$. We reverse interval $[4,5]$, and $p$ becomes $[1,2,3,4,5]$, with cost $w_{4,5}=2$.

As you can see, after the $i$-th step ends, the positions $[1,i]$ of the sequence are exactly the clothes labeled $[1,i]$. After the algorithm finishes, $p$ is sorted. The total cost of this sorting is $4+2+2+2=10$.

Note: The algorithm will always execute $n-1$ steps, and it will not terminate early even if it becomes sorted in the middle.

[Constraints and Hints]

Hint: The input size of this problem is large, so please avoid overly slow input methods.

• For $25\%$ of the testdata, $1 \le n \le 9$.
• For $50\%$ of the testdata, $1 \le n \le 16$.
• For $70\%$ of the testdata, $1 \le n \le 50$.
• For another $15\%$ of the testdata, $w_{i,j}=1$.
• For $100\%$ of the testdata, $1 \le n \le 500$, $0 \le w_{i,j} < 998244353$.

Translated by ChatGPT 5