题目描述

如果有一个 $1 \sim n$ 的排列 $p_1,p_2,\ldots,p_n$，假设存在这样一个排序算法：按 $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$，以此类推，知道 $n-1$ 步全部执行完成。且该算法一定会执行 $n − 1$ 步，即使中间就排好了序也不会提前退出。

我们假设左右翻转区间 $[i,j]$ 的操作代价是 $a_{i,j}$，一次排序的代价是每次翻转的操作代价之和。现在请你计算出，当 $p$ 取遍 $n!$ 种排列时，所有情况的排序代价之和，并对答案模 $998244353$。

输入格式

输入第一行，一个整数 $n$。 接下来 $n-1$ 行，第 $i(1 \le i \lt n)$ 行 $n - i + 1$ 个空格隔开的整数，第 $j$ 个表示 $a_{i,i+j-1}$。

输出格式

输出共一个正整数，表示所求答案。

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

1080

数据范围

• 对于$20\%$的数据，$1\leq n \leq 10$
• 对于$50\%$的数据，$1\leq n \leq 16$
• 对于$70\%$的数据，$1\leq n \leq 50$
• 对于$100\%$的数据，$1\leq n \leq 500$ , $1 \leq a_{i,j} \leq 998244353$