Pic1. 베이징 동로
Pic2. 베이징 동로
Pic3. 난징 동로
테러리스트들이 $n$개 도시의 베이징 동로에 폭탄을 설치했으며, 초기 $i$번째 도시의 폭탄 위력은 $a_i$입니다.
테러리스트들은 $k$번의 폭발을 일으키기로 했습니다. $i$번째 도시에서 폭발이 일어날 때의 위험도는 해당 도시의 폭탄 위력 $a_i$입니다. 매 폭발 후, 테러리스트가 에너지를 조절하여 폭탄의 총 위력을 일정하게 유지하기 때문에, 모든 $j\neq i$에 대해 $a_j$는 $\frac{a_i}{n-1}$만큼 증가하고, $a_i$는 $0$이 됩니다.
하지만 테러리스트의 원격 폭발 시스템이 고장 나서, 매번 무작위로 하나의 도시를 선택하여 폭발시킵니다.
방어를 위해, 소 S는 $k$번의 폭발 후 $i$번째 도시의 폭탄 위력 $a_i$의 기댓값이 얼마인지 알고 싶어 합니다. 결과를 $998244353$으로 나눈 나머지를 구하세요.
입력 형식
첫 번째 줄에 두 개의 양의 정수 $n, k$가 주어집니다.
두 번째 줄에 $n$개의 양의 정수 $a_i$가 주어집니다.
출력 형식
한 줄에 $n$개의 정수를 출력하며, 이는 각 도시의 기댓값을 의미합니다.
예제
입력 1
6 3 2 1 0 0 3 5
출력 1
381994841 86514512 789278536 789278536 677475170 270191475
입력 2
2 1 1 2
출력 2
499122178 499122178
데이터 범위
| 서브태스크 번호 | 배점 | 추가 제한 |
|---|---|---|
| 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 | 없음 |
모든 데이터에 대하여: $2\leq n\leq10^6$, $1\leq k\leq10^9$, $0\leq a_i<998244353$입니다.