Hikamura Nakaru is a famous Xiangqi player and streamer who has defeated the champion Carlos Magnussen once (and lost ~14~ times). Today, Hikamura is interacting with ~m~ contestants of the VNOI Cup 2025. Of course, with his skills, Hikamura can easily defeat all the contestants. Therefore, to increase the excitement, the VNOI Cup organizers have prepared ~n~ challenges for Hikamura, ranging from simple challenges like "time handicap" or "handicap a pawn" to more complex challenges like "the knight cannot move backward." The ~i~-th challenge has a difficulty of ~a_i~. The organizers can choose any number of challenges for a game.

The probability of Hikamura winning a game depends on the difficulty of the challenges in that game. Specifically, let ~S~ be the set of challenges chosen for the game, the probability that Hikamura wins this game is:

$$1 - \frac{\sum_{j \in S} a_j}{\sum_{j=1}^{n} a_j}$$

Accordingly, if all challenges are chosen, Hikamura will definitely lose; conversely, if no challenges are chosen, he will definitely win.

Hikamura plays the first game with ~0~ challenges (~S = \varnothing~). After each game Hikamura wins, the organizers will randomly select a challenge ~i \notin S~ and add it to ~S~ for the next game. The probability that challenge ~i~ is chosen is:

$$\frac{a_i}{\sum_{j \notin S} a_j}$$

Similarly, after each game Hikamura loses, the organizers will randomly remove a challenge ~i \in S~ from ~S~ for the next game. The probability that challenge ~i~ is removed is:

$$\frac{a_i}{\sum_{j \in S} a_j}$$

Hikamura will play ~m~ games, one game with each contestant of the VNOI Cup. MofK, a member of the organizing committee, wants to know the expected number of games Hikamura will win, but since he is not very good at probability, he decided that the contestants of the VNOI Cup must solve this problem before they can play. Please help the contestants!

Input

The first line contains an integer ~t~ (~1 \leq t \leq 10\,000~) — the number of test cases. Each test case is described as follows:

The first line contains two positive integers ~n~, ~m~ (~1 \leq n \leq 10\,000~, ~1 \leq m \leq 10^9~) — the number of challenges presented by the organizers and the number of games Hikamura will play.

The second line contains ~n~ positive integers ~a_1, a_2, \ldots, a_n~ (~1 \leq a_i \leq 10\,000~) — the difficulty of each challenge.

It is guaranteed that the sum of ~n~ across all test cases does not exceed ~2 \cdot 10^5~.

Output

For each test case, output a single integer which is the expected number of games Hikamura will win, modulo ~998\,244\,353~. Specifically, if the answer can be expressed as a simplified fraction ~\frac{p}{q}~, output the non-negative integer ~s < 998\,244\,353~ where ~q \cdot s = p \pmod {998\,244\,353}~.

Scoring

Sample Input 1

4
4 1
1 4 2 3
4 2
1 4 2 3
2 3
1 1
10 420
31 41 59 26 53 58 97 93 23 84

Sample Output 1

1
99824437
2
172856962

Notes

In the first example, Hikaru plays exactly one game of chess. Since initially ~S = \varnothing~, Hikaru will definitely win this game, so the expected number of wins for Hikaru is ~1~.

In the second example, Hikaru plays ~m = 2~ games of chess, with ~a = [1, 4, 2, 3]~, and ~\sum_{i = 1}^4 a_i = 10~. After winning the first game, there are 4 possible outcomes, corresponding to 4 ways to choose a challenge to add to the set ~S~, as shown in the table below:

Thus, the expected number of wins for Hikaru is:

$$1 + \left( \frac{1}{10} \cdot \frac{9}{10} + \frac{4}{10} \cdot \frac{6}{10} + \frac{2}{10} \cdot \frac{8}{10} + \frac{3}{10} \cdot \frac{7}{10} \right) = 1 + \frac{70}{100} = \frac{17}{10}$$

Note that we add ~1~ because Hikaru has already won the first game. We output ~998\,244\,37~ since ~17 \equiv 998\,244\,37 \cdot 10 \pmod{998\,244\,353}~.

In the third example, Hikaru plays ~m = 3~ games of chess. Both challenges have ~a_i = 1~, so we can consider the two challenges equivalent.

After winning the first game, one challenge is added to the set ~S~. The probability of winning the second game is ~\frac{1}{2}~.

• If Hikaru wins the second game, Hikaru will lose the third game, as all challenges have been chosen.

• If Hikaru loses the second game, Hikaru will win the third game, as no challenges have been chosen.

Thus, the expected number of wins for Hikaru is:

$$1 + \frac{1}{2} \cdot (1 + 0) + \frac{1}{2} \cdot (0 + 1) = 2$$