题目描述

有一个长度为 $N$ 的整数序列 $a=(a_1,a_2,\cdots,a_N)$，所有元素初始均为 $0$。

给定整数 $C$ 和 $M$ 个区间 $([L_1,R_1],[L_2,R_2],\cdots,[L_M,R_M])$。

你需要选择 $1$ 到 $M$ 的一个排列 $p$，以及一个长度为 $M$ 的整数序列 $w=(w_1,w_2,\cdots,w_M)$，其中 $1\le w_i\le C$。

然后进行 $M$ 次操作。第 $i$ 次操作如下：

• 将 $a_{L_{p_i}},\cdots,a_{R_{p_i}}$ 的值全部变为 $w_i$。

保证 $a$ 的每个位置至少被一个区间覆盖。

请计算所有可能的最终序列 $a$ 的种数，并输出对 $998244353$ 取模的结果。

输入格式

输入从标准输入中读取，格式如下：

$N$ $M$ $C$ $L_1$ $R_1$ $L_2$ $R_2$ $\cdots$ $L_M$ $R_M$

输出格式

输出答案。

样例 1

输入

5 5 2
1 3
2 2
3 3
1 5
3 5

输出

16

样例 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

输出

258066445

说明/提示

限制条件

• $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$ 的每个位置至少被一个区间覆盖。
• 所有输入均为整数。

样例解释 1

可能的序列共有 $16$ 个。例如，$a=(2,1,1,1,1)$ 可以如下得到：

• 选择 $p=(4,1,2,3,5)$ 和 $w=(1,2,1,2,1)$
• 第 $1$ 次操作后 $a$ 变为 $(1,1,1,1,1)$
• 第 $2$ 次操作后 $a$ 变为 $(2,2,2,1,1)$
• 第 $3$ 次操作后 $a$ 变为 $(2,1,2,1,1)$
• 第 $4$ 次操作后 $a$ 变为 $(2,1,2,1,1)$
• 第 $5$ 次操作后 $a$ 变为 $(2,1,1,1,1)$

由 ChatGPT 4.1 翻译