分数: 2200 点
问题陈述
您有一个简单的无向图。 该图中的每个顶点都写有一个整数区间,并且有 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