Problem Description

There is a positive integer sequence $a$ of length $n$, with values in $[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\limits_{j=l_i}^{r_i}\{a_j\}$. Find how many different $b$ can be obtained when $a$ can be chosen arbitrarily within the range. Output the answer modulo $998244353$.

Input Format

The first line contains three integers, which are $n,m,c$ in order.

The next $m$ lines each contain two integers $l_i,r_i$, representing a given interval.

Output Format

Output one line containing one integer, the answer.

3 2 2
1 2
2 3

4

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

129

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

567581188

Hint

For $100\%$ of the testdata, $1\le n\le 100,1\le m\le\dfrac{n(n+1)}{2},1\le c<998244353,\forall i\in [1,m],1\le l_i\le r_i\le n$. It is guaranteed that the given $m$ intervals are pairwise distinct.

$\operatorname{Subtask}1(5\%):n,c\le 5$.

$\operatorname{Subtask}2(10\%):c\le 100$, and for any two intervals that intersect, one of them must contain the other.

$\operatorname{Subtask}3(15\%):m\le 18,c=2$.

$\operatorname{Subtask}4(20\%):c=2$.

$\operatorname{Subtask}5(15\%):n,c\le 40$.

$\operatorname{Subtask}6(15\%):c\le 100$.

$\operatorname{Subtask}7(20\%):$ No special constraints.

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)$.

Therefore, a total of $4$ different $b$ can be obtained: $[1,1],[1,2],[2,1],[2,2]$.

Translated by ChatGPT 5