# 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 **x _{1}**, …,

**x**.. At the each moment of time evolution is described by the following system of linear equations:

_{n}** x ^{i+1}_{1}** =

**a**+ … +

_{11}x^{i}_{1}**a**

_{1n}x^{i}_{n}…

** x ^{i+1}_{n}** =

**a**+ … +

_{n1}x^{i}_{1}**a**

_{nn}x^{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**). Then one line that contains

^{9}**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**", where

^{M}_{n}**A**is the number of test (beginning from 1),

**x**, …,

^{M}_{1}**x**are the desired numbers for this test case.

^{M}_{n}2 1 5 2 1 2 7 14 26 32 45 534 623

Case #1: 32 Case #2: 62813 87846