题目描述

正の整数 $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$)

输入格式

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

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

输出格式

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

题目大意

给定一个整数 $M$ 和一个序列 $\{A_N\}$，计数值域为 $[1,M]$ 的序列个数 $\{X_{N+1}\}$ 满足 $\forall i\in[1,N] A_iX_i\leqslant X_{i+1}$，答案对 $998244353$ 取模。

2 10
2 3

7

2 10
3 2

9

7 1000
1 2 3 4 3 2 1

225650129

5 1000000000000000000
1 1 1 1 1

307835847

提示

制約

• $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$

Sample Explanation 1

条件を満たす整数列 $X$ は、以下の $7$ 個です： - $(1,\ 2,\ 6)$, $(1,2,7)$, $(1,2,8)$, $(1,2,9)$, $(1,2,10)$, $(1,3,9)$, $(1,3,10)$

Sample Explanation 2

条件を満たす整数列 $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)$