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.