题目描述
有一个长度为 $n$，值域为 $[1,c]$ 的正整数序列 $a$。给定 $m$ 个区间 $[l_i, r_i]$，设长度为 $m$ 的序列 $b$ 满足 $\forall i\in [1,m],b_i=\min\limits_{j=l_i}^{r_i}\{a_j\}$。求出 $a$ 在范围内任意取的情况下共能得到多少种不同的 $b$。答案对 998244353 取模。
输入格式
第一行，三个数，依次表示 $n, m, c$。
接下来 $m$ 行，每行两个数 $l_i, r_i$ 表示一个给定的区间。
输出格式
共一行，一个数，表示答案。
样例数据
样例输入 1
3 2 2
1 2
2 3样例输出 1
4样例说明 1
当 $a=(1,1,1)$ 时，$b=(1,1)$。
当 $a=(1,1,2)$ 时，$b=(1,1)$。
当 $a=(1,2,1)$ 时，$b=(1,1)$。
当 $a=(1,2,2)$ 时，$b=(1,2)$。
当 $a=(2,1,1)$ 时，$b=(1,1)$。
当 $a=(2,1,2)$ 时，$b=(1,1)$。
当 $a=(2,2,1)$ 时，$b=(2,1)$。
当 $a=(2,2,2)$ 时，$b=(2,2)$。
因此共能得到 $(1,1),(1,2),(2,1),(2,2)$ 这 $4$ 种不同的 $b$。
样例输入 2
10 11 2
1 10
2 2
3 3
5 5
6 10
6 7
6 6
7 7
8 10
8 9
10 10样例输出 2
129样例说明 2
这个样例满足 $\operatorname{Subtask}2\sim 7$ 的限制。
样例输入 3
40 40 40
31 34
9 34
4 25
36 38
8 29
8 30
6 26
17 19
6 23
36 39
11 39
2 10
32 37
32 33
33 35
17 21
8 35
31 40
11 25
11 20
8 37
26 36
22 34
17 39
28 38
26 28
11 12
12 15
12 37
1 9
11 23
5 26
8 11
1 23
12 32
7 19
22 28
20 27
8 40
19 40样例输出 3
567581188样例说明 3
这个样例满足 $\operatorname{Subtask}5\sim 7$ 的限制。
数据范围
对于 $100 \%$ 的数据， $1 \leq n \leq 100,1 \leq m \leq \frac{n(n+1)}{2}, 1 \leq c < 998244353, \forall i \in[1, m], 1 \leq l_i \leq r_i \leq n$ 。保证给定的 $m$ 个区间两两不同。
- Subtask $1(5 \%)$: $n, c \leq 5$ 。
- Subtask $2(10 \%)$: $c \leq 100$ ，且对于任意两个有交的区间一定存在其中一个包含另一个。
- Subtask $3(15 \%)$: $m \leq 18, c=2$ 。
- Subtask $4(20 \%)$: $c = 2$ 。
- Subtask $5(15 \%)$: $n, c \leq 40$ 。
- Subtask $6(15\%)$: $c \leq 100$ 。
- Subtask $7(20 \%)$: 无特殊限制。