Laundry Sorting Cost Sum

You are given n clothes, each having a unique label from \(1\) to \(n\). Initially, the clothes are arranged in a sequence \(p_1, p_2, \dots, p_n\). A sorting algorithm is defined as follows:

For \(i = 1, 2, \dots, n-1\), let \(j\) be the index of the minimum element in the subarray \(p_i, p_{i+1}, \dots, p_n\). Then, reverse the subarray \(p_i, p_{i+1}, \dots, p_j\) (i.e. transform it into \(p_j, p_{j-1}, \dots, p_i\)). Each reversal operation on the interval \([i,j]\) has an associated cost \(w_{i,j}\) (given as input).

The cost of sorting a permutation is the sum of the costs of all reversal operations performed by the algorithm. When \(p\) runs over all \(n!\) permutations, your task is to compute the sum of sorting costs over all these permutations, and output the answer modulo \(998244353\) (which is a prime number).

Note: For a fixed \(i\) (with \(1 \le i \le n-1\)), the reversal operation is applied on the interval \([i,j]\) if the minimum in \(p_i, p_{i+1}, \dots, p_n\) is at position \(j\). It can be shown that for each \(j\) (with \(i \le j \le n\)), there are exactly \(\frac{n!}{n-i+1}\) permutations where the minimum element in \(p_i, p_{i+1}, \dots, p_n\) is at position \(j\). Equivalently, the contribution of a given reversal \([i,j]\) is \((i-1)!\,(n-i)!\,w_{i,j}\), and the overall required sum is \(\sum_{i=1}^{n-1}\sum_{j=i}^{n}(i-1)!\,(n-i)!\,w_{i,j}\).

inputFormat

The first line contains a single integer \(n\) (the number of clothes).

The following \(n\) lines each contain \(n\) integers. The \(j\)th integer on the \(i\)th line represents \(w_{i,j}\) (the cost to reverse the interval \([i,j]\)). It is guaranteed that the costs for all intervals \(1 \le i \le j \le n\) are provided (even though some entries with \(i > j\) may be ignored).

outputFormat

Output a single integer — the sum of sorting costs over all \(n!\) permutations modulo \(998244353\).

sample

2
1 2
3 4

3