题目描述

你有一个简单无向图。该图的每个顶点上都写有一个整数区间，区间 $[i,j]$（$1 \leq i \leq j \leq N$）的顶点有 $C_{i,j}$ 个。此外，没有其他区间的顶点。

对于任意两个顶点，这两个顶点之间存在一条无向边当且仅当它们所写的区间有交集。这里，区间 $[a,b]$ 和区间 $[c,d]$ 有交集是指 $\max(a,c) \leq \min(b,d)$。

请你求出该图的生成树个数，并将结果对 $998244353$ 取模。

所有顶点都是互不相同、可区分的。

输入格式

输入通过标准输入给出，格式如下：

$N$ $C_{1,1}$ $C_{1,2}$ $\cdots$ $C_{1,N}$ $C_{2,2}$ $\cdots$ $C_{2,N}$ $\vdots$ $C_{N,N}$

输出格式

输出答案。

样例 1

输入

2
1 2
1

输出

8

样例 2

输入

3
1 1 1
1 1
1

输出

99

样例 3

输入

4
8 3 8 10
1 5 3
1 6
4

输出

971555314

样例 4

输入

10
2742 5611 1401 5439 5220 8571 4998 4194 7443 2492
2393 3201 9106 1649 2456 1984 7159 9679 7695
808 4600 2573 7771 5839 9504 4381 3223
5325 2564 456 5050 6963 913 9072
310 1521 9816 6205 2988 3614
4810 2979 2852 9242 6290
7551 7139 7228 699
4869 889 7597
4239 5970
865

输出

234850531

说明/提示

限制

• $2 \leq N \leq 400$
• $1 \leq C_{i,j} \leq 10^4$
• 输入的所有数均为整数。

由 ChatGPT 4.1 翻译