Problem Statement

We have $N$ boxes numbered $1$ to $N$. Initially, Box $i$ contains $A_i$ balls.

You will repeat the following operation $K$ times.

• Choose one box out of the $N$ uniformly at random (each time independently). Add one ball to the chosen box.

Let $B_i$ be the number of balls in Box $i$ after the $K$ operations, and the score be the product of the numbers of balls, $\prod_{i=1}^{N}B_i$.

Find the expected value of the score modulo $998244353$.

Note

When the expected value in question is represented as an irreducible fraction $p/q$, there uniquely exists an integer $r$ such that $rq\equiv p \pmod{998244353}$ and $0\leq r < 998244353$ under the Constraints of this problem. This $r$ is the value we seek.

Constraints

• $1 \leq N \leq 1000$
• $1 \leq K \leq 10^9$
• $0 \leq A_i \leq 10^9$

Input

Input is given from Standard Input in the following format:

N K
A_1 \ldots A_N

Output

Print the answer.