Problem Description

There is an integer sequence $a=(a_1,a_2,\cdots,a_N)$ of length $ N $. Initially, all elements are $ 0 $.

You are given an integer $ C $ and $ M $ intervals $([L_1,R_1],[L_2,R_2],\cdots,[L_M,R_M])$.

You will choose a permutation $ p $ of $(1,2,\cdots,M)$ and an integer sequence $w=(w_1,w_2,\cdots,w_M)$ of length $ M $. Here, $1\le w_i\le C$ must hold.

Then, you will perform $ M $ modifications. The $ i $-th modification is as follows:

• Change $a_{L_{p_i}},\ \cdots,\ a_{R_{p_i}}$ to $ w_i $.

It is guaranteed that every position in $ a $ is covered by at least one interval.

Find the number of possible sequences $ a $ after all modifications, and output the answer modulo $ 998244353 $.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

16

Sample Input #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

Sample Output #2

258066445

Notes/Hints

Constraints

• $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$)
• Every position in $ a $ is covered by at least one interval.
• All input values are integers.

Sample Explanation 1

There are $ 16 $ possible sequences. For example, $ a=(2,1,1,1,1) $ can be obtained as follows:
- Choose $ p=(4,1,2,3,5) $ and $ w=(1,2,1,2,1) $
- After the 1st operation, $ a $ becomes $ (1,1,1,1,1) $
- After the 2nd operation, $ a $ becomes $ (2,2,2,1,1) $
- After the 3rd operation, $ a $ becomes $ (2,1,2,1,1) $
- After the 4th operation, $ a $ remains $ (2,1,2,1,1) $
- After the 5th operation, $ a $ becomes $ (2,1,1,1,1) $

见题面 Input 部分

见题面 Output 部分