问题陈述

给定一个正整数 $M$ 和一个整数序列 $A = (A_1,A_2,\\ldots,A_N)$。计算满足以下条件的整数序列 $X = (X_1,X_2, \\ldots, X_{N+1})$ 的数量，取模 $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$

输出

输出满足条件的整数序列的数量，取模 $998244353$。

示例输入 1

2 10
2 3

示例输出 1

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

满足条件的九个整数序列如下：

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