Симуляция процесса
Вам задан некоторый дискретный эволюционный процесс. В каждый момент времени состояние процесса описывается параметрами x[1], …, x[n]. В каждый момент времени эволюция описывается следующей системой линейных уравнений:
x[1]^(i+1) = a[11]x[1]^i + … + a[1n]x[n]^i
…
x[n]^(i+1) = a[n1]x[1]^i + … + a[nn]x[n]^i
Найдите состояние процесса в момент времени M. Каждый параметр должен быть посчитан по модулю 100007.
Входные данные
Первая строка ввода содержит количество тестов T (1 ≤ T ≤ 10). Первая строка каждого теста содержит 2 числа: N, (1 ≤ N ≤ 100) – количество параметров и M (0 ≤ M ≤ 10^9) – момент времени. Далее следуют N строк, каждая из которых содержит N целых чисел, разделённых пробелами. j-е число в i-й строке – a[ij] (0 ≤ a[ij] ≤ 10^9). Далее следуют одна строка, содержащая N целых чисел. j-е число в этой строке – x[j]^0 (0 ≤ x[j]^0 ≤ 10^9).
Выходные данные
Выведите T строк вида Case #A: x[1]^M … x[n]^M, где A – номер теста (начиная с 1), x[1]^M, …, x[n]^M – искомые параметры для данного теста.