Process Simulation#103
Sign in

Process Simulation

15 seconds
64 megabytes
Medium

You are given a discrete evolution process. At each moment, the state of the process is described by parameters x_1, x_2, \ldots, x_n. The evolution at each moment is determined by the following system of linear equations:

x^{i+1}_1 = a_{11} x^i_1 + a_{12} x^i_2 + \ldots + a_{1n} x^i_n \\ \cdots \\ x^{i+1}_n = a_{n1} x^i_1 + a_{n2} x^i_2 + \ldots + a_{nn} x^i_n

Find the state of the process at moment . Each parameter should be computed modulo .

Input

The first line contains (1 \le T \le 100), the number of test cases. Each test case begins with a line containing two integers: (1 \le N \le 100), the number of parameters, and (0 \le M \le 10^9), the moment in time. Then lines follow, each containing integers separated by spaces. The -th integer in the -th line is a_{ij} (0 \le a_{ij} \le 10^9). Then, one more line follows, containing integers: the -th integer is x^0_j (0 \le x^0_j \le 10^9).

Output

Output lines, each in the format Case #: x^M_1 x^M_2 x^M_n, where is the test case number (starting from ), and x^M_1, \ldots, x^M_n are the required parameters for that test case.

Examples

Example 1

Loading
Loading