E - Encriptando listas

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

Fito está estudiando algoritmos de encriptación, después de aprender algunos, él decidió hacer el suyo propio. Su algoritmo es muy simple:  Fito dispone de una lista de $N$ $(1 \leq N \leq 10^6)$ enteros $A_i$ $(0 \leq A_i \lt 10^9)$, entonces sustituye cada $A_i$ por la suma de los otros $N - 1$ números en la lista. Después de jugar un rato con este algoritmo Fito concluye que es muy fácil de romper, por esto decidió aplicarlo $T$ veces $(1 \leq T \leq 10^{15})$. Su primera versión era simple de llevar en una hoja pero con la nueva modificación algún código debe ser escrito, por esto Fito le ha pedido que lo ayude calculando los números finales después de aplicar $T$ veces su algoritmo a una lista inicial $A$.

Input

La primera línea contiene dos enteros separados por espacio $N$ y $T$. La segunda línea describe la lista $A$ con $N$ enteros separados por espacio.

Output

Una línea con $N$ enteros separados por espacio, la lista después de aplicar $T$ veces el algoritmo de encriptación de Fito a los números de la entrada. Los números en la salida pueden ser demasiado grandes así que usted debe calcularlos módulo $98765431$.

Sample test(s)

Input
3 4 1 0 4
Output
26 25 29

Hints

Descripción del ejemplo

#

A1

A2

A3

0

1

0

4

1

4

5

1

2

6

5

9

3

14

15

11

4

26

25

29