Problem Statement

binap loves playing with dolls. He always seats his dolls around a round table to recreate a tea party, and he suddenly began to wonder how many ways there are to seat them.

binap has $N$ kinds of dolls, and there are $A_i$ dolls of the $i$-th kind. The round table can seat $K$ dolls at equal intervals. No seat may be left empty.

Please find the number of ways to seat the dolls. Since the answer can be very large, output the remainder when it is divided by the prime $998244353$.

Two seatings are considered different if and only if no rotation of the round table in the plane can make the kinds of all the seated dolls match.

Constraints

• $1 \leq N \leq 3\times10^5$

• $2 \leq K \leq 1300$

• $1 \leq A_i \leq 998244352(1\leq i \leq N)$

• $K \leq \sum_{i=1}^N A_i$

• All inputs are integers.

Input

$N$ $K$
$A_1$ $A_2$ $\cdots$ $A_N$

Output

Output the total number of seatings modulo $998244353$.

Sample

3 3
2 1 1

4

3 6
3 4 1

32

5 4
4 4 3 2 1

128

14 14
1 1 1 1 1 1 1 1 1 1 1 1 1 1

237554682