AT_abc457_f.Second Gap

You are given an integer $N$ and an integer sequence $D = (D_1, D_2, \ldots, D_{N-1})$ of length $N - 1$.

Find the number, modulo $998244353$, of permutations $P = (P_1, P_2, \ldots, P_N)$ of $(1, 2, \ldots, N)$ that satisfy the following condition.

• For each $1 \le i \le N - 1$, let $P_a$ and $P_b$ be the elements with the largest and the second largest values, respectively, among $(P_i, P_{i+1}, \ldots, P_N)$; then $|a - b| = D_i$.

给定一个整数 $N$ 和一个长度为 $N - 1$ 的整数序列 $D = (D_1, D_2, \ldots, D_{N-1})$。

求满足以下条件的排列 $P = (P_1, P_2, \ldots, P_N)$（即 $(1, 2, \ldots, N)$ 的一个排列）的个数，答案对 $998244353$ 取模。

• 对每个 $1 \le i \le N - 1$，设 $P_a$ 和 $P_b$ 分别为子序列 $(P_i, P_{i+1}, \ldots, P_N)$ 中最大值和次大值所对应的元素；则需满足 $|a - b| = D_i$。

The input is given from Standard Input in the following format:

$N$
$D_1$ $D_2$ $\ldots$ $D_{N-1}$

输入从标准输入中按以下格式给出：

$N$
$D_1$ $D_2$ $\ldots$ $D_{N-1}$

Output the number, modulo $998244353$, of permutations satisfying the condition.

输出满足该条件的排列数量，对 $998244353$ 取模。

Sample 1 Explanation:
For example, we can verify that $(2, 3, 1)$ satisfies the condition as follows.

• We have $(P_1, P_2, P_3) = (2, 3, 1)$. The largest value is $P_2$ and the second largest value is $P_1$, and $|2 - 1| = 1 = D_1$.

• We have $(P_2, P_3) = (3, 1)$. The largest value is $P_2$ and the second largest value is $P_3$, and $|2 - 3| = 1 = D_2$.

Four permutations satisfy the condition: $(1, 2, 3), (1, 3, 2), (2, 3, 1), (3, 2, 1)$. Thus, output $4$.

Constraints

• $2 \le N \le 2 \times 10^5$
• $1 \le D_i \le N - i$
• All input values are integers.

样例 1 解释：
例如，我们可以验证排列 $(2, 3, 1)$ 满足条件，如下所示。

• 此时 $(P_1, P_2, P_3) = (2, 3, 1)$。其中最大值为 $P_2$，次大值为 $P_1$，且 $|2 - 1| = 1 = D_1$。
• 此时 $(P_2, P_3) = (3, 1)$。其中最大值为 $P_2$，次大值为 $P_3$，且 $|2 - 3| = 1 = D_2$。

共有四个排列满足条件：$(1, 2, 3),\ (1, 3, 2),\ (2, 3, 1),\ (3, 2, 1)$。因此输出 $4$。

约束条件

• $2 \le N \le 2 \times 10^5$
• $1 \le D_i \le N - i$
• 所有输入值均为整数。