There is a sequence $a$ of length $n$ with values in the range $[1, c]$. Given $m$ intervals $[l_i, r_i]$, let $b$ be a sequence of length $m$ such that $\forall i \in [1, m], b_i = \min_{j=l_i}^{r_i} \{a_j\}$. Find the total number of distinct sequences $b$ that can be obtained as $a$ varies over all possible sequences. The answer should be taken modulo 998244353.

Input

The first line contains three integers $n, m, c$.

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

Output

A single integer representing the answer.

Examples

Input 1

3 2 2
1 2
2 3

Output 1

4

Note 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 sequences $b$ that can be obtained: $(1,1), (1,2), (2,1), (2,2)$.

Input 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 2

129

Note 2

This example satisfies the constraints for Subtasks $2 \sim 7$.

Input 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 3

567581188

Note 3

This example satisfies the constraints for Subtasks $5 \sim 7$.

Constraints

For $100\%$ of the data, $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$. It is guaranteed that the $m$ given intervals are distinct.

• Subtask $1 (5\%)$: $n, c \leq 5$.
• Subtask $2 (10\%)$: $c \leq 100$, and for any two intersecting intervals, one must contain the other.
• 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\%)$: No special constraints.