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.

​【​​题目​​描述​**】**

没想到在如此发达的 2077 年，城市中还能碰到沙尘暴，这超现实的场景让小雪怀疑是妖怪显灵。

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

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

小可可还想到，我们可以把一段连续的晾衣架拿出来，在手上翻转顺序，再放回去。作为OI选手的你，马上抽象出了小可可排序衣服的算法：我们设初始时从左往右第i件衣服的标号为pi，按1,2,…,n-1的顺序枚举i，设p​~i~​,p​~i+1~​,…,p~n~中标号最小的是p​~j~​，那么将p​~i~​,p​~i+1~​,…,p​~j−1~​,p~j~左右翻转变成p​~j~​,p​~j−1~​,…,p​~i+1~​,p​~i~​。我们假设左右翻转区间[i,j]的操作代价是w​~i,j~​，一次排序的代价是每次翻转的操作代价之和。

现在小可可想知道，当p取遍n!种排列时，所有情况的排序代价之和。只用输出答案对998244353取模后的值。

​【​​​输入​**】**

第一行一个整数 n。

下面 n-1 行，第 i(1 ≤ i ≤ n) 行 n-i + 1 个空格隔开的整数，第 j 个表示 w​~i,j~​。

​【​​​输出​**】**

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

​【​​输​入​样例​​1​**】**

5

1 2 3 4 5

1 2 3 4

1 2 3

1 2

​【​​输​出​样例​​1​**】**

1080

**【样例1说明】 **

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

• 执行到 i = 1，p1, p2, p3, p4, p5 即 3, 2, 5, 1, 4 中的最小值为 p4 = 1，我们翻转区间 [1, 4]，p 变为 [1, 5, 2, 3, 4]，代价为 w1,4 = 4；

• 执行到 i = 2，p2, p3, p4, p5 即 5, 2, 3, 4 中的最小值为 p3 = 2，我们翻转区间 [2, 3]，p 变为 [1, 2, 5, 3, 4]，代价为 w2,3 = 2；

• 执行到 i = 3，p3, p4, p5 即 5, 3, 4 中的最小值为 p4 = 3，我们翻转区间 [3, 4]，p 变为 [1, 2, 3, 5, 4]，代价为 w3,4 = 2；

• 执行到 i = 4，p4, p5 即 5, 4 中的最小值为 p5 = 4，我们翻转区间 [4, 5]，p 变为 [1, 2, 3, 4, 5]， 代价为 w4,5 = 2。

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

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

**【样例2】 **

见下发文件的 其他样例/sort2.in 和 其他样例/sort2.ans。

​【​​​数据说明​**】**

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

对于 25% 的数据，保证 1 ≤ n ≤ 9；

对于 50% 的数据，保证 1 ≤ n ≤ 16；

对于 70% 的数据，保证 1 ≤ n ≤ 50；

对于另外 15% 的数据，保证 w~i,j~ = 1；

对于 100% 的数据，保证 1 ≤ n ≤ 500, 0 ≤ w~i,j~ < 998244353。

样例