Process simulation
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
First line of input contains the quantity of tests T (1 ≤ T ≤ 10). First line of each test case contains two numbers: N, (1 ≤ N ≤ 100) – the number of parameters and M (0 ≤ M ≤ 10^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 (0 ≤ a_ij ≤ 10^9). Then one line that contains N integers follows. j-th number in this line is x^0_j (0 ≤ x^0_j ≤ 10^9).
Output
Output T lines of the form "Case #A: x^M_1 … x^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.