AT_arc118_f [ARC118F] Growth Rate

[problemUrl]: https://atcoder.jp/contests/arc118/tasks/arc118_f 正の整数 $ 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 $ で出力してください。

### 制約 - $ 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) $