题目背景

Polaris_Dane 非常菜，他不仅沉迷于计数，而且喜欢玩星际争霸 2。

题目描述

「我的好兄弟无穷无尽，而你的虫子每时每刻都在消亡」

作为新上任爱民如子的指挥官，Polaris_Dane 充分领悟了雷诺指挥官的智慧，决定将此战术贯彻到底。

有 $N$ 个兵营，依次编号为 $1,2,3\cdots N$。现在需要把它们排列在一条数轴中位于 $[1,M]$ 间的整点处。每一个兵营都有一个生产范围 $r_i$，若兵营放在点 $x\ (1 \le x \le M)$ 处，那么它会在区间 $[x - r_i + 1, x + r_i - 1]$ 生产好兄弟。

当 $\rm type = 0$ 时，生产好兄弟的范围必须被区间 $[1,M]$ 完全包含；当 $\rm type = 1$ 时，生产好兄弟的范围可以落在 $[1,M]$ 之外，但是兵营必须放在 $[1,M]$ 内。

Polaris_Dane 不能让好兄弟们太挤了，所以任何两个兵营的生产范围 都不能相交，他想知道有多少种方案满足该条件。

若两个方案中存在一个编号为 $i$ 的兵营，其在两个方案中的放置位置不同，则称这两个方案不同。

由于答案可能很大，所以 Polaris_Dane 想请你输出答案对 $998244353$ 取模后的结果。

输入格式

第一行三个整数 $N, M, \mathrm{type}$，其中 $\rm type \in \{0, 1\}$。

第二行 $N$ 个整数 $r_1, r_2, r_3, \ldots, r_n$。

输出格式

仅一行一个整数，为所求的答案对 $998244353$ 取模后的结果。

4 4 0
1 1 1 1

24

4 4 1
1 1 1 1

24

3 47 1
4 8 9

10940

8 100000 1
21 37 23 13 32 22 9 39

405170260

提示

样例解释：

在样例 1 中，无论如何摆放兵营，生产范围都不会交叉，所以答案即为 $A_4^4 = 24$。

在样例 2 中，虽然生产范围可以出界，但是兵营的可选位置还是只有 $4$ 种，答案仍是 $A_4^4 = 24$。

---

对于所有数据：

• $1 \le N, M \le 10^6$；
• $1 \le r_i \le 1000$。

---

本题采用捆绑测试。

No.	Constraints	$\rm type$	Score
$1$	$N = 2;\ M \le 1000;\ r_i = 1$	$0$	$10$
$2$	$N = 2;\ M \le 10^6;\ r_i = 1$
$3$	$N \le 40;\ M \le 10^6;\ r_i = 1$
$4$	No further constraints		$30$
$5$	$N, r_i \le 40$	$1$	$20$
$6$	No further constraints

---

• Idea: Polaris_Dane
• Solution: Polaris_Dane
• Code: Polaris_Dane
• Data: Polaris_Dane