Вам задано деякий дискретний еволюційний процес. У кожен момент часу стан процесу описується параметрами \textbf{x_1}, …, \textbf{x_n}. У кожен момент часу еволюція описується наступною системою лінійних рівнянь: \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} Знайдіть стан процесу в момент часу \textbf{M}. Кожен параметр повинен бути порахованим за модулем \textbf{100007}. \InputFile Перший рядок містить кількість тестів \textbf{T} (\textbf{1} ≤ \textbf{T} ≤ \textbf{10}). Перший рядок кожного тесту містить \textbf{2} числа: \textbf{N}, (\textbf{1} ≤ \textbf{N} ≤ \textbf{100}) -- кількість параметрів і \textbf{M} (\textbf{0} ≤ \textbf{M} ≤ \textbf{10^9}) -- момент часу. Далі йде \textbf{N} рядків, кожен з яких містить \textbf{N} цілих чисел, відокремлених пропусками. \textbf{j}-е число в \textbf{i}-й рядку -- \textbf{a_ij} (\textbf{0} ≤ \textbf{a_ij} ≤ \textbf{10^9}). Далі йде один рядок, що містить \textbf{N} цілих чисел. \textbf{j}-е число в цьому рядку -- \textbf{x^0_j} (\textbf{0} ≤ \textbf{x^0_j} ≤ \textbf{10^9}). \OutputFile Виведіть \textbf{T} рядків вигляду "Case #\textbf{A}: \textbf{x^M_1} … \textbf{x^M_n}", де \textbf{A} -- номер тесту (починаючи з 1), \textbf{x^M_1}, …, \textbf{x^M_n} -- шукані параметри для даного тесту.