题目描述
Problem Description
There is a sequence \( a \) of length \( n \) with values ranging from \( [1, c] \). Given \( m \) intervals \( [l_i, r_i] \), define a sequence \( b \) of length \( m \) such that \( \forall i \in [1, m], b_i = \min_{j=l_i}^{r_i} \{a_j\} \). Calculate the number of distinct \( b \) sequences that can be obtained by arbitrarily choosing \( a \) within the given range. The answer should be taken modulo \( 998244353 \).
Input Format
The first line contains three numbers: \( n \), \( m \), and \( c \).
The next \( m \) lines each contain two numbers \( l_i \) and \( r_i \) representing a given interval.
Output Format
Output a single number, which is the answer.
Sample Input and Output
Input Sample #1
3 2 2
1 2
2 3
Output Sample #1
4
Input Sample #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
Output Sample #2
129
Input Sample #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
Output Sample #3
567581188
Notes/Hints
For \( 100\% \) of the data, \( 1 \le n \le 100, 1 \le m \le \frac{n(n+1)}{2}, 1 \le c < 998244353, \forall i \in [1, m], 1 \le l_i \le r_i \le n \). The given \( m \) intervals are guaranteed to be distinct.
- Subtask 1 (5%): \( n, c \le 5 \).
- Subtask 2 (10%): \( c \le 100 \), and for any two intersecting intervals, one must contain the other.
- Subtask 3 (15%): \( m \le 18, c = 2 \).
- Subtask 4 (20%): \( c = 2 \).
- Subtask 5 (15%): \( n, c \le 40 \).
- Subtask 6 (15%): \( c \le 100 \).
- Subtask 7 (20%): No special restrictions.
Sample Explanation 1
When \( a = (1, 1, 1) \), \( b = (1, 1) \).
When \( a = (1, 1, 2) \), \( b = (1, 1) \).
When \( a = (1, 2, 1) \), \( b = (1, 1) \).
When \( a = (1, 2, 2) \), \( b = (1, 2) \).
When \( a = (2, 1, 1) \), \( b = (1, 1) \).
When \( a = (2, 1, 2) \), \( b = (1, 1) \).
When \( a = (2, 2, 1) \), \( b = (2, 1) \).
When \( a = (2, 2, 2) \), \( b = (2, 2) \).
Thus, there are \( 4 \) distinct \( b \) sequences: \( [1, 1], [1, 2], [2, 1], [2, 2] \).
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分