Given a positive integer M and N positive integers a₁, a₂, ..., a_N. Count the number of non-negative integer tuples (x₁, x₂, ..., x_N) such that:

a₁ * x₁ + a₂ * x₂ + ... + a_N * x_N = M

Input

- The first line contains two integers N and M.

- The second line contains N integers a₁, a₂, ..., a_N respectively.

Output

- Output only one integer, the number of asked tuples modulo 998244353.

Constrains

• 1 ≤ N ≤ 60 000
• 1 ≤ M ≤ 10¹⁸
• 1 ≤ a_i ≤ 60 000
• 1 ≤ a₁ + a₂ + ... + a_N ≤ 60 000

Example

Input:

3 10
3 2 5

Output:

4

Input:

5 100000
1 3 4 6 1000

Output:

865762992

Note

• My solution runs in less than 0.8s for each input file, 6.3s in total.