favorite We need a little bit of your help to keep things running, click on this banner to learn more

Process simulation

Process simulation

You are given some discrete evolution process. At each moment of time the state of the process is described by parameters x1, …, xn.. At the each moment of time evolution is described by the following system of linear equations:

xi+11 = a11xi1 + … + a1nxin

xi+1n = an1xi1 + … + annxin

Find the process state at the moment M. Each parameter should be calculated modulo 100007.


First line of input contains the quantity of tests T (1T10). First line of each test case contains two numbers: N, (1N100) – the number of parameters and M (0M109) – moment of time. Then N lines follows, each of which contains N integers separated by spaces. j-th number in i-th line is aij (0aij109). Then one line that contains N integers follows. j-th number in this line is x0j (0x0j109).


Output T lines of the form "Case #A: xM1xMn", where A is the number of test (beginning from 1), xM1, …, xMn are the desired numbers for this test case.

Time limit 15 seconds
Memory limit 64 MiB
Input example #1
1 5
2 7
14 26
32 45
534 623
Output example #1
Case #1: 32
Case #2: 62813 87846