AT_abc457_f [ABC457F] Second Gap

整数 $ N $ と長さ $ N - 1 $ の整数列 $ D = (D_1, D_2, \ldots, D_{N-1}) $ が与えられます。 $ (1, 2, \ldots, N) $ の順列 $ P = (P_1, P_2, \ldots, P_N) $ であって、次の条件を満たすものの個数を $ 998244353 $ で割った余りを求めてください。 - すべての $ 1 \le i \le N - 1 $ について、 $ (P_i, P_{i+1}, \ldots, P_N) $ の中で最大の値を持つ要素を $ P_a $ 、 $ 2 $ 番目に大きい値を持つ要素を $ P_b $ とすると $ |a - b| = D_i $ である。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ D_1 $ $ D_2 $ $ \ldots $ $ D_{N-1} $

条件を満たす順列の個数を $ 998244353 $ で割った余りを出力せよ。

### Sample Explanation 1 例えば $ (2, 3, 1) $ が条件を満たしていることは、以下のように確認できます。 - $ (P_1, P_2, P_3) = (2, 3, 1) $ である。最大の値は $ P_2 $ 、 $ 2 $ 番目に大きい値は $ P_1 $ であり $ |2 - 1| = 1 = D_1 $ である。 - $ (P_2, P_3) = (3, 1) $ である。最大の値は $ P_2 $ 、 $ 2 $ 番目に大きい値は $ P_3 $ であり $ |2 - 3| = 1 = D_2 $ である。 条件を満たす順列は $ (1, 2, 3), (1, 3, 2), (2, 3, 1), (3, 2, 1) $ の $ 4 $ つです。よって $ 4 $ を出力してください。 ### Constraints - $ 2 \le N \le 2 \times 10^5 $ - $ 1 \le D_i \le N - i $ - 入力される値はすべて整数