AT_agc067_b [AGC067B] Modifications

有一个长度为 $N$ 的整数序列 $a=(a_1,a_2,\cdots,a_N)$，所有元素初始均为 $0$。 给定整数 $C$ 和 $M$ 个区间 $([L_1,R_1],[L_2,R_2],\cdots,[L_M,R_M])$。 你需要选择 $1$ 到 $M$ 的一个排列 $p$，以及一个长度为 $M$ 的整数序列 $w=(w_1,w_2,\cdots,w_M)$，其中 $1\le w_i\le C$。 然后进行 $M$ 次操作。第 $i$ 次操作如下： - 将 $a_{L_{p_i}},\cdots,a_{R_{p_i}}$ 的值全部变为 $w_i$。 保证 $a$ 的每个位置至少被一个区间覆盖。 请计算所有可能的最终序列 $a$ 的种数，并输出对 $998244353$ 取模的结果。

输入从标准输入中读取，格式如下： > $N$ $M$ $C$ $L_1$ $R_1$ $L_2$ $R_2$ $\cdots$ $L_M$ $R_M$

输出答案。

### 限制条件 - $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$） - $a$ 的每个位置至少被一个区间覆盖。 - 所有输入均为整数。 ### 样例解释 1 可能的序列共有 $16$ 个。例如，$a=(2,1,1,1,1)$ 可以如下得到： - 选择 $p=(4,1,2,3,5)$ 和 $w=(1,2,1,2,1)$ - 第 $1$ 次操作后 $a$ 变为 $(1,1,1,1,1)$ - 第 $2$ 次操作后 $a$ 变为 $(2,2,2,1,1)$ - 第 $3$ 次操作后 $a$ 变为 $(2,1,2,1,1)$ - 第 $4$ 次操作后 $a$ 变为 $(2,1,2,1,1)$ - 第 $5$ 次操作后 $a$ 变为 $(2,1,1,1,1)$ 由 ChatGPT 4.1 翻译