You are given some discrete evolution process. At each moment of time the state of the process is described by parameters \textbf{x_1}, …, \textbf{x_n}.. At the each moment of time evolution is described by the following system of linear equations: \textbf{x^\{i+1\}_1} = \textbf{a_11x^i_1} + … + \textbf{a_1nx^i_n} … \textbf{x^\{i+1\}_n} = \textbf{a_n1x^i_1} + … + \textbf{a_nnx^i_n} Find the process state at the moment \textbf{M}. Each parameter should be calculated modulo \textbf{100007}. \InputFile First line of input contains the quantity of tests \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{10}). First line of each test case contains two numbers: \textbf{N}, (\textbf{1} ≤ \textbf{N} ≤ \textbf{100}) -- the number of parameters and \textbf{M} (\textbf{0} ≤ \textbf{M} ≤ \textbf{10^9}) -- moment of time. Then \textbf{N} lines follows, each of which contains \textbf{N} integers separated by spaces. \textbf{j}-th number in \textbf{i}-th line is \textbf{a_ij} (\textbf{0} ≤ \textbf{a_ij} ≤ \textbf{10^9}). Then one line that contains \textbf{N} integers follows. \textbf{j}-th number in this line is \textbf{x^0_j} (\textbf{0} ≤ \textbf{x^0_j} ≤ \textbf{10^9}). \OutputFile Output \textbf{T} lines of the form "Case #\textbf{A}: \textbf{x^M_1} … \textbf{x^M_n}", where \textbf{A} is the number of test (beginning from 1), \textbf{x^M_1}, …, \textbf{x^M_n} are the desired numbers for this test case.