eolymp
bolt
Try our new interface for solving problems
Problems

Process simulation

Process simulation

Time limit 15 seconds
Memory limit 64 MiB

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

x^{i+1}_1 = a_11x^i_1 + … + a_1nx^i_n

x^{i+1}_n = a_n1x^i_1 + … + a_nnx^i_n

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

Input data

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 (0M10^9) – moment of time. Then N lines follows, each of which contains N integers separated by spaces. j-th number in i-th line is a_ij (0a_ij10^9). Then one line that contains N integers follows. j-th number in this line is x^0_j (0x^0_j10^9).

Output data

Output T lines of the form "Case #A: x^M_1x^M_n", where A is the number of test (beginning from 1), x^M_1, …, x^M_n are the desired numbers for this test case.

Examples

Input example #1
2
1 5
2
1
2 7
14 26
32 45
534 623
Output example #1
Case #1: 32
Case #2: 62813 87846