P7501 「HMOI R1」50 块好兄弟

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$ 取模后的结果。

样例解释： 在样例 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$ | $0$ | $10$ | | $3$ | $N \le 40;\ M \le 10^6;\ r_i = 1$ | $0$ | $10$ | | $4$ | No further constraints | $0$ | $30$ | | $5$ | $N, r_i \le 40$ | $1$ | $20$ | | $6$ | No further constraints | $1$ | $20$ | ------ - Idea: Polaris_Dane - Solution: Polaris_Dane - Code: Polaris_Dane - Data: Polaris_Dane