問題文

長さ $N-1$ の整数列 $A = (A_1, \ldots, A_{N - 1})$ が与えられます。

長さ $N$ の整数列 $B = (B_0, B_1, \ldots, B_{N - 1})$ を $B_0 = 1, B_i = A_iB_{i - 1} (1 \leq i < N)$ と定義します。

整数 $M$ が与えられるので以下の式を満たすような長さ $N$ の非負整数列 $C = (C_0, C_1, \ldots, C_{N - 1})$ の個数を求めてください。 $$ \displaystyle \sum_{i = 0}^{N-1} B_i C_i = M $$ 答えは非常に大きくなりうるので $998244353$ で割った余りを求めてください。

入力

$N$
$A_1\ \cdots\ A_{N - 1}$
$M$

• $1 \leq N \leq 2000$
• $2 \leq A_i \leq 2000 (1 \leq i < N)$
• $1 \leq M < 10^{7000}$
• 入力は全て整数

出力

答えを $998244353$ で割ったあまりを出力してください。最後に改行してください。

サンプル

3
2 2
5

4

1

13

1

7
6 2 8 5 8 2
866311

770044952