You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

AHOI2021 初中组 T3

你可以选择跳过背景部分。

沉迷于虐待跳蚤游戏的小雪没有发觉时间过了多久，一抬头发现竟然天色大变！天空一片昏黄，一股怪味扑鼻而来。没想到在如此发达的 2077 年，城市中还能碰到沙尘暴，这超现实的场景让小雪怀疑是跳蚤国王显灵。

“别愣着了，快去收衣服呀！”小可可突然想到。

题目描述

看着这么多蒙灰的衣服，他们俩欲哭无泪；而且，有的衣服是没法一起洗的，为了分门别类，小可可给了每件衣服一个 $1 \sim n$ 的两两不同的标号，其中 $n$ 是衣服的件数，把衣服排成 $1,2,\ldots,n$ 的顺序再洗会比较方便。

小可可还想到，我们可以把一段连续的晾衣架拿出来，在手上翻转顺序，再放回去。作为 OI 选手的你，马上抽象出了小可可排序衣服的算法：我们设初始时从左往右第 $i$ 件衣服的标号为 $p_i$，按 $1,2,\ldots,n-1$ 的顺序枚举 $i$，设 $p_i,p_{i+1},\ldots,p_n$ 中标号最小的是 $p_j$，那么将 $p_i,p_{i+1},\ldots,p_{j-1},p_j$ 左右翻转变成 $p_j,p_{j-1},\ldots,p_{i+1},p_i$。

小雪很快发现，小可可的算法看似厉害，实际上很傻——在天色的影响下，大家都分不出衣服的标号了。于是他们只能回到房间进行理性愉悦：我们假设左右翻转区间 $[i,j]$ 的操作代价是 $w_{i,j}$，一次排序的代价是每次翻转的操作代价之和。现在小可可想知道，当 $p$ 取遍 $n!$ 种排列时，所有情况的排序代价之和。

只用输出答案对 $998244353$（$=7 \times 17 \times 2^{23} + 1$，一个质数）取模后的值。

输入格式

第一行一个整数 $n$。

下面 $n-1$ 行，第 $i(1 \le i \le n)$ 行 $n - i + 1$ 个空格隔开的整数，第 $j$ 个表示 $w_{i,j}$。

输出格式

一行一个整数，表示答案对 $998244353$ 取模的结果。

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

1080

见附加文件的 sort2.in。 

见附加文件的 sort2.ans。

提示

【样例 1 解释】

我们举一个例子，当 $p=[3,2,5,1,4]$ 时，算法的执行步骤如下：

• 执行到 $i=1$，$p_1,p_2,p_3,p_4,p_5$ 即 $3,2,5,1,4$ 中的最小值为 $p_4=1$，我们翻转区间 $[1,4]$，$p$ 变为 $[1,5,2,3,4]$，代价为 $w_{1,4}=4$；
• 执行到 $i=2$，$p_2,p_3,p_4,p_5$ 即 $5,2,3,4$ 中的最小值为 $p_3=2$，我们翻转区间 $[2,3]$，$p$ 变为 $[1,2,5,3,4]$，代价为 $w_{2,3}=2$；
• 执行到 $i=3$，$p_3,p_4,p_5$ 即 $5,3,4$ 中的最小值为 $p_4=3$，我们翻转区间 $[3,4]$，$p$ 变为 $[1,2,3,5,4]$，代价为 $w_{3,4}=2$；
• 执行到 $i=4$，$p_4,p_5$ 即 $5,4$ 中的最小值为 $p_5=4$，我们翻转区间 $[4,5]$，$p$ 变为 $[1,2,3,4,5]$，代价为 $w_{4,5}=2$。

可以看到，算法执行到第 $i$ 步结束时，序列的 $[1,i]$ 位置上恰好是 $[1,i]$ 号衣服，算法结束后 $p$ 被排好了序。这次排序总共付出了 $4+2+2+2=10$ 的代价。

注意：算法一定会执行 $n-1$ 步，即使中间就排好了序也不会提前退出。

【数据范围与提示】

提示：本题输入规模较大，请避免使用过慢的输入方式。

• 对于 $25\%$ 的数据，保证 $1 \le n \le 9$；
• 对于 $50\%$ 的数据，保证 $1 \le n \le 16$；
• 对于 $70\%$ 的数据，保证 $1 \le n \le 50$；
• 对于另外 $15\%$ 的数据，保证 $w_{i,j}=1$；
• 对于 $100\%$ 的数据，保证 $1 \le n \le 500$，$0 \le w_{i,j} < 998244353$。