e-olymp
Problems

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.

Input

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

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
2
1 5
2
1
2 7
14 26
32 45
534 623
Output example
Case #1: 32
Case #2: 62813 87846