Вам задан некоторый дискретный эволюционный процесс. В каждый момент времени состояние процесса описывается параметрами x1, …, xn. В каждый момент времени эволюция описывается следующей системой линейных уравнений:

x1^(i+1) = a11x1^i + … + a1nxn^i

…

xn^(i+1) = an1x1^i + … + annxn^i

Найдите состояние процесса в момент времени M. Каждый параметр должен быть посчитан по модулю 100007.

Входные данные

Первая строка ввода содержит количество тестов T (1 ≤ T ≤ 10). Первая строка каждого теста содержит 2 числа: N, (1 ≤ N ≤ 100) – количество параметров и M (0 ≤ M ≤ 109) – момент времени. Далее следуют N строк, каждая из которых содержит N целых чисел, разделённых пробелами. j-е число в i-й строке – aij (0 ≤ aij ≤ 109). Далее следуют одна строка, содержащая N целых чисел. j-е число в этой строке – xj^0 (0 ≤ xj^0 ≤ 109).

Выходные данные

Выведите T строк вида Case #A: x1^M … xn^M, где A – номер теста (начиная с 1), x1^M, …, xn^M – искомые параметры для данного теста.