分数: 1100 点
问题陈述
你有一个整数序列 a=(a_1,a_2,\cdots,a_N) 长度 N。 所有元素最初都是 0.
给你一个整数 C 和 M 间隔 ([L_1,R_1],[L_2,R_2],\cdots,[L_M,R_M]).
您将选择一个排列 p of (1,2,\cdots,M) 和一个整数序列 w=(w_1,w_2,\cdots,w_M) 长度 M。 在这里, 1\le w_i\le C 必须保留。
然后,你会做 M 修改。 的 i-第修改如下:
- 更改 a_{L_{p_i}}, \cdots, a_{R_{p_i}} to w_i.
保证每个位置 a 被至少一个区间覆盖。
找出可实现的数量 a 完成所有修改后。 打印答案取模 998244353.
约束
- 1\le N\le 100
- 1\le M\le\dfrac{N(N+1)}{2}
- 1\le C<998244353
- 1 \le L_i \le R_i \le N
- (L_i,R_i) \neq (L_j,R_j) (i \neq j)
- 中的每个位置 a 被至少一个区间覆盖。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M C L_1 R_1 L_2 R_2 \vdots L_M R_M
输出
打印答案。
示例输入 1
5 5 2 1 3 2 2 3 3 1 5 3 5
示例输出 1
16
有 16 可以实现的序列。 例如,您可以实现 a=(2,1,1,1,1) 按以下方式:
- 选择 p=(4,1,2,3,5) 和 w=(1,2,1,2,1)
- 的 1-st 操作更改 a 进入 (1,1,1,1,1)
- 的 2-nd 操作更改 a 进入 (2,2,2,1,1)
- 的 3-rd 操作更改 a 进入 (2,1,2,1,1)
- 的 4-第操作更改 a 进入 (2,1,2,1,1)
- 的 5-第操作更改 a 进入 (2,1,1,1,1)
示例输入 2
20 30 20 1 14 1 7 1 16 3 13 1 17 4 8 2 11 4 12 9 14 3 15 11 19 1 13 4 15 8 19 3 17 15 18 10 18 1 18 17 19 16 20 1 8 8 15 13 17 1 19 13 19 1 20 6 13 10 12 11 20 17 18
示例输出 2
258066445