SUMSUMS  Summing Sums
The N (1 ≤ N ≤ 50,000) cows, conveniently numbered 1, 2, ..., N, are trying to learn some encryption algorithms. After studying a few examples, they have decided to make one of their own! However, they are not very experienced at this, so their algorithm is very simple:
Each cow i is given a starting number C_{i} (0 ≤ C_{i} < 90,000,000), and then all the cows perform the following process in parallel:
 First, each cow finds the sum of the numbers of the other N1 cows.
 After all cows are finished, each cow replaces her number with the sum she computed. To avoid very large numbers, the cows will keep track of their numbers modulo 98,765,431.
They told Canmuu the moose about it in November; he was quite impressed. Then one foggy Christmas Eve, Canmuu came to say:
"Your algorithm is too easy to break! You should repeat it T (1 ≤ T ≤ 1,414,213,562) times instead."
Obviously, the cows were very frustrated with having to perform so many repetitions of the same boring algorithm, so after many hours of arguing, Canmuu and the cows reached a compromise: You are to calculate the numbers after the encryption is performed!
Input
 Line 1: Two spaceseparated integers: N and T.
 Lines 2..N+1: Line i+1 contains a single integer: C_{i}.
Output
 Lines 1..N: Line i contains a single integer representing the number of cow i (modulo 98,765,431) at the end of the encryption.
Example
Input: 3 4 1 0 4 Output: 26 25 29
The following is a table of the cows' numbers for each turn:
Cows' numbers Turn Cow1 Cow2 Cow3 0 1 0 4 1 4 5 1 2 6 5 9 3 14 15 11 4 26 25 29Warning: large input/output data.
hide comments
smso:
20191126 04:55:03
Use matrix exponentiation. There are only 2 distinct values (in the diagonal and offdiagonal respectively) in any intermediate step. Python3 is able to pass the grader. 

rocky1729:
20191115 11:22:39
@agarwal117


kesh4281:
20190809 13:44:18
even if u get a wrong on test case #1, the program still runs until last case. So don't get confused that u r only getting WA in last case only.


agrawal117:
20190801 16:33:22
very nice problem!!


aayush_b1999:
20190710 23:05:42
i wasn't doing modulus for sum of initial values.that's why i was getting wrong answer in test 14. so there might be problem with how you are doing mod. hope it helps other's problem. Last edit: 20190711 07:21:41 

grucha78:
20190602 16:51:15
Is it possible to get "Accepted" in Java? My program runs locally 0.03s for maximum set size, yet I get TLE. 

infyy:
20180601 10:15:44
Getting WA in last test case even though I have used 98765431 

druh:
20171201 14:24:58
WA on 14 :( Help PLEASE!


fresh:
20160127 04:14:24
sorry for that


fresh:
20160126 14:49:21
there is something wrong with this problem

Added by:  Neal Wu 
Date:  20080528 
Time limit:  0.160s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 
Resource:  USACO Chn 2007 