Problem Statement

You have an integer sequence $a=(a_1,a_2,\cdots,a_N)$ of length $N$. All elements are initially $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 do $M$ modifications. The $i$-th modification is the following:

• 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 achievable $a$ after all modifications. Print the answer modulo $998244353$.

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.

Input

Input is given from Standard Input in the following format:

N M C
L_1 R_1
L_2 R_2
\vdots
L_M R_M

Output

Print the answer.