Симуляция процесса
Симуляция процесса
Вам задан некоторый дискретный эволюционный процесс. В каждый момент времени состояние процесса описывается параметрами 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
– искомые параметры для данного теста.
2 1 5 2 1 2 7 14 26 32 45 534 623
Case #1: 32 Case #2: 62813 87846