Pic1. Đường Bắc Kinh Đông
Pic2. Đường Bắc Kinh Đông
Pic3. Đường Nam Kinh Đông
Những kẻ khủng bố đã cài bom tại $n$ thành phố trên đường Bắc Kinh Đông, với sức công phá ban đầu của quả bom tại thành phố thứ $i$ là $a_i$.
Những kẻ khủng bố quyết định thực hiện $k$ vụ nổ. Trong một vụ nổ tại thành phố $i$, mức độ nguy hiểm bằng với sức công phá $a_i$ của quả bom tại thành phố đó. Sau mỗi vụ nổ, vì những kẻ khủng bố có thể điều khiển năng lượng để giữ cho tổng sức công phá của các quả bom không đổi, với mọi $j \neq i$, $a_j$ sẽ tăng thêm $\frac{a_i}{n-1}$, trong khi $a_i$ sẽ trở về $0$.
Tuy nhiên, hệ thống kích nổ từ xa của những kẻ khủng bố đã bị hỏng, mỗi lần nó sẽ chọn ngẫu nhiên một thành phố để kích nổ.
Để thuận tiện cho việc phòng thủ, Tiểu S muốn biết sau $k$ vụ nổ, giá trị kỳ vọng của sức công phá $a_i$ tại thành phố $i$ là bao nhiêu, kết quả lấy modulo $998244353$.
Dữ liệu vào
Dòng đầu tiên gồm hai số nguyên dương $n, k$.
Dòng thứ hai gồm $n$ số nguyên dương $a_i$.
Dữ liệu ra
Một dòng gồm $n$ số nguyên dương, biểu thị các giá trị kỳ vọng.
Ví dụ
Dữ liệu vào 1
6 3 2 1 0 0 3 5
Dữ liệu ra 1
381994841 86514512 789278536 789278536 677475170 270191475
Dữ liệu vào 2
2 1 1 2
Dữ liệu ra 2
499122178 499122178
Giới hạn
| Số thứ tự subtask | Điểm | Hạn chế bổ sung |
|---|---|---|
| 1 | 20 | $n,k\leq 5$ |
| 2 | 20 | $n,k\leq 10^3$ |
| 3 | 25 | $k\leq 10^6$ |
| 4 | 15 | $a_1=1,a_2=a_3=\dots=a_n=0$ |
| 5 | 20 | Không có |
Với tất cả các dữ liệu: $2\leq n\leq10^6$, $1\leq k\leq10^9$, $0\leq a_i<998244353$.