Image 1. Route de Beijing East
Image 2. Route de Beijing East
Image 3. Route de Nanjing East
Des terroristes ont installé des bombes dans $n$ villes sur la route de Beijing East. Initialement, la puissance de la bombe dans la ville $i$ est $a_i$.
Les terroristes décident d'effectuer $k$ explosions. Lors d'une explosion dans la ville $i$, le niveau de danger est égal à la puissance de la bombe dans cette ville, $a_i$. Après chaque explosion, comme les terroristes peuvent manipuler l'énergie pour maintenir la puissance totale des bombes constante, pour tout $j \neq i$, $a_j$ augmente de $\frac{a_i}{n-1}$, tandis que $a_i$ devient nul.
Cependant, le système de détonation à distance des terroristes est défectueux et choisit à chaque fois une ville au hasard pour l'explosion.
Pour faciliter la défense, Xiao S souhaite connaître l'espérance mathématique de la puissance $a_i$ des bombes dans chaque ville $i$ après $k$ explosions, modulo $998244353$.
Entrée
La première ligne contient deux entiers positifs $n, k$.
La deuxième ligne contient $n$ entiers positifs $a_i$.
Sortie
Une ligne contenant $n$ entiers, représentant les espérances mathématiques.
Exemples
Entrée 1
6 3 2 1 0 0 3 5
Sortie 1
381994841 86514512 789278536 789278536 677475170 270191475
Entrée 2
2 1 1 2
Sortie 2
499122178 499122178
Contraintes
| Numéro de sous-tâche | Score | Contraintes supplémentaires |
|---|---|---|
| 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 | Aucune |
Pour toutes les données : $2\leq n\leq10^6$, $1\leq k\leq10^9$, $0\leq a_i<998244353$.