問題文

正の整数 $M$ と、$N$ 項からなる整数列 $A = (A_1,A_2,\\ldots,A_N)$ が与えられます。$N+1$ 項からなる整数列 $X = (X_1,X_2, \\ldots, X_{N+1})$ であって、次の条件をすべて満たすものの個数を $\\bmod 998244353$ で求めてください。

• $1\\leq X_i\\leq M$ ($1\\leq i\\leq N+1$)
• $A_iX_i\\leq X_{i+1}$ ($1\\leq i\\leq N$)

制約

• $1\\leq N\\leq 1000$
• $1\\leq M\\leq 10^{18}$
• $1\\leq A_i\\leq 10^9$
• $\\prod_{i=1}^N A_i \\leq M$

入力

入力は以下の形式で標準入力から与えられます。

$N$ $M$ $A_1$ $A_2$ $\\ldots$ $A_N$

出力

条件を満たす整数列の個数を $\\bmod 998244353$ で出力してください。

入力例 1

2 10
2 3

出力例 1

7

条件を満たす整数列 $X$ は、以下の $7$ 個です：

• $(1, 2, 6)$, $(1,2,7)$, $(1,2,8)$, $(1,2,9)$, $(1,2,10)$, $(1,3,9)$, $(1,3,10)$

入力例 2

2 10
3 2

出力例 2

9

条件を満たす整数列 $X$ は、以下の $9$ 個です：

• $(1, 3, 6)$, $(1, 3, 7)$, $(1, 3, 8)$, $(1, 3, 9)$, $(1, 3, 10)$, $(1, 4, 8)$, $(1, 4, 9)$, $(1, 4, 10)$, $(1, 5, 10)$

入力例 3

7 1000
1 2 3 4 3 2 1

出力例 3

225650129

入力例 4

5 1000000000000000000
1 1 1 1 1

出力例 4

307835847