P8502 「CGOI-2」No cost too great

光芒浸透圣巢，她正犯下弥天之错。 所剩寥寥无几的信仰，为什么始终执着。 我将作灯塔，照耀王国。 但在那之前有更重要的事去做， 无论什么代价都在所不惜，尽管我所剩无多……

白王正在最后一次参观他建造的宏伟宫殿。现在假设宫殿由 $n$ 个房间构成，房间之间有若干个**单向**通道。出于白王奇怪的装修癖好（不是指到处安电锯），对于第 $i$ 个房间，它向编号在区间 $[l_i,r_i]$ 中的所有房间都连有一条单向通道。例如，$4$ 号房间向 $[2,5]$ 连有单向通道，就意味着从 $4$ 号房间到 $2,3,4,5$ 号房间各有一条单向通道（一个房间可以向自己连有通道）。当一个房间向 $[0,0]$ 连有通道时，表示没有从这个房间出发的通道。 白王提出了 $q$ 个问题，每次询问从 $a$ 号房间，通过恰好 $m$ 条单向通道且不经过 $c$ 号房间到达 $b$ 号房间的方案数（两方案不同，当且仅当存在 $i$ 使得两方案通过的第 $i$ 条通道不同）。因为这个数字可能会很大，所以白王让你将答案模 $998244353$ 后再回答。

无

无

### 样例说明 在样例一中，$1$ 号房间能到达 $2,3$ 号房间，$2$ 号房间能到达 $1$ 号房间，$3$ 号房间能到达 $2,3,4$ 号房间，$4$ 号房间不能到达任何房间。 对于第一个询问，从 $1$ 号房间经过 $5$ 条通道且不经过 $4$ 号房间到达 $3$ 号房间的方案有 `121213`，`121333`，`133213`，`132133`，`133333` 共五种。 --- ### 数据范围 **本题采用捆绑测试。** | 编号| 特殊性质 | 空间限制 |分数 | | :-: | :-: | :-: | :-: | | 0 | $n\le10$，$q\le10$，$m\le4$ | 256MB | 10pts | | 1 | $n\le100$，$q\le10^4$，$m\le40$ | 256MB | 15pts | | 2 | 对于所有询问，$l_c=r_c=0$ | 256MB | 15pts | | 3 | 无 | 256MB | 30pts | | 4 | 无 | 128MB | 30pts | 对于 $100\%$ 的数据，$1\le n \le 500$，$1\le q \le 10^5$，$1\le m \le 100$，$0 \le l_i \le r_i \le n$，$1 \le a,b,c \le n$。当且仅当 $l_i=0$ 时 $r_i=0$。时间限制均为 1s。 --- ### 提示 **注意空间常数。**