题目背景

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

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

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

题目描述

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

小可可还想到，我们可以把一段连续的晾衣架拿出来，在手上翻转顺序，再放回去。作为 OI 选手的你，马上抽象出了小可可排序衣服的算法：我们设初始时从左往右第 $i$ 件衣服的标号为 $p_i$， 按 $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$（$= 7 × 17 × 2^{23} + 1$，一个质数）取模后的值。

输入格式

输入文件名为 sort.in。

第一行一个整数 $n$。

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

输出格式

输入文件名为 sort.out。

一行一个整数表示答案对 $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$，$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 ≤ n ≤ 9$；

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

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

• 对于另外 15% 的数据，保证 $w_{i,j} = 1$；

• 对于 100% 的数据，保证 $1 ≤ n ≤ 500$， $0 ≤ w_{i,j} < 998244353$。