Hikamura Nakaru là một kì thủ cờ tướng và streamer nổi tiếng, người từng đánh bại kỳ vương Carlos Magnussen một lần (và thua ~14~ lần). Hôm nay, Hikamura giao lưu với ~m~ thí sinh của kì thi VNOI Cup 2025. Dĩ nhiên, với khả năng của mình, Hikamura có thể dễ dàng đánh bại tất cả các thí sinh. Do vậy, để tăng sự hấp dẫn, ban tổ chức VNOI Cup đã chuẩn bị sẵn ~n~ thử thách cho Hikamura, từ những thử thách đơn giản như "chấp thời gian" hay "chấp một quân tốt" cho đến những thử thách phức tạp hơn như "quân mã không được đi lùi". Thử thách thứ ~i~ có độ khó ~a_i~. Ban tổ chức có thể chọn bao nhiêu thử thách tùy ý cho một ván cờ.

Xác suất thắng của Hikamura ở một ván cờ phụ thuộc vào độ khó của các thử thách trong ván cờ đó. Cụ thể, gọi ~S~ là tập các thử thách được chọn của ván cờ, xác suất để Hikamura thắng ván cờ này là:

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

Theo đó, nếu tất cả các thử thách đều được chọn thì Hikamura chắc chắn thua; ngược lại, nếu không có thử thách nào được chọn thì anh chắc chắn thắng.

Hikamura chơi ván đầu tiên với ~0~ thử thách (~S = \varnothing~). Sau mỗi ván Hikamura thắng, ban tổ chức sẽ chọn một thử thách ngẫu nhiên ~i \notin S~ và thêm vào ~S~ cho ván tiếp theo. Xác suất thử thách ~i~ được chọn là:

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

Tương tự, sau mỗi ván Hikamura thua, ban tổ chức sẽ loại một thử thách ngẫu nhiên ~i \in S~ khỏi ~S~ cho ván tiếp theo. Xác suất thử thách ~i~ được bỏ là:

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

Hikamura sẽ chơi ~m~ ván cờ, một ván với mỗi thí sinh VNOI Cup. MofK, một thành viên ban tổ chức muốn biết giá trị kì vọng số ván thắng của Hikamura, tuy nhiên do học xác suất hơi kém nên MofK quyết định bắt các thí sinh VNOI Cup giải được bài toán này mới được chơi cờ. Hãy giúp các thí sinh nhé!

Input

Dòng đầu tiên chứa số nguyên ~t~ (~1 \leq t \leq 10\,000~) – số lượng test case. Mô tả của mỗi test case như sau:

Dòng đầu tiên chứa hai số nguyên dương ~n~, ~m~ (~1 \leq n \leq 10\,000~, ~1 \leq m \leq 10^9~)  – số thử thách ban tổ chức đưa ra và số ván cờ Hikamura sẽ chơi.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \leq a_i \leq 10\,000~)  – độ khó của mỗi thử thách.

Đảm bảo rằng tổng ~n~ qua tất cả các test case không vượt quá ~2 \cdot 10^5~.

Output

Với mỗi test case, in ra một số nguyên duy nhất là giá trị kì vọng số ván thắng của Hikamura, modulo ~998\,244\,353~. Cụ thể, nếu đáp án được biểu diễn dưới dạng phân số tối giản ~\frac{p}{q}~, in ra số nguyên không âm ~s < 998\,244\,353~ sao cho ~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

Trong ví dụ đầu tiên, Hikaru chỉ chơi đúng một ván cờ. Do ban đầu ~S = \varnothing~, Hikaru chắc chắn sẽ chiến thắng ván cờ này, nên kì vọng số ván thắng của Hikaru là ~1~.

Trong ví dụ thứ hai, Hikaru chơi ~m = 2~ ván cờ, với ~a = [1, 4, 2, 3]~, và ~\sum_{i = 1}^4 a_i = 10~. Sau khi chiến thắng ván đấu đầu tiên, có 4 khả năng xảy ra, tương ứng với 4 cách chọn thử thách để thêm vào tập ~S~, được thể hiện qua bảng sau:

Như vậy kì vọng số ván thắng của Hikaru là:

$$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}$$

Lưu ý ta cộng thêm ~1~ vì Hikaru đã thắng ván đấu đầu tiên. Ta in ra ~998\,244\,37~ do ~17 \equiv 998\,244\,37 \cdot 10 \pmod{998\,244\,353}~

Ở ví dụ thứ 3, Hikaru chơi ~m = 3~ ván cờ. Hai thử thách đều có ~a_i = 1~, do đó ta có thể coi hai thử thách tương đương nhau.

Sau khi thắng ván đấu đầu tiên, một thử thách được thêm vào tập ~S~. Xác suất chiến thắng ván đấu thứ hai là ~\frac{1}{2}~.

• Nếu thắng ván thứ hai, Hikaru sẽ thua ván thứ ba, do tất cả các thử thách đều đã được chọn.

• Nếu thua ván thứ hai, Hikaru sẽ thắng ván thứ ba, do không có thử thách nào được chọn.

Như vậy kì vọng số ván thắng của Hikaru là:

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