← 返回题目列表

AtCoder · agc060_f

F. 区间图的生成树

中文机器翻译题面 查看原题

分数: 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