题目描述

你有一个简单的无向图。这个图中的每个顶点上都有一个整数区间，并且有 $C_{i,j}$ 个顶点具有区间 \[i,j\] ($1 \leq i \leq j \leq N$)。没有其他区间的顶点。

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

求这个图的生成树数量，对 $998244353$ 取模。这里，所有顶点都是可区分的。

约束条件

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

输入

从标准输入中按以下格式给出输入：

$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

样例输出 1

8

样例输入 2

3
1 1 1
1 1
1

样例输出 2

99

样例输入 3

4
8 3 8 10
1 5 3
1 6
4

样例输出 3

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

样例输出 4

234850531