e-olymp
Задачі

Симуляція процесу

Симуляція процесу

Вам задано деякий дискретний еволюційний процес. У кожен момент часу стан процесу описується параметрами x1, …, xn. У кожен момент часу еволюція описується наступною системою лінійних рівнянь:

xi+11 = a11xi1 + … + a1nxin

xi+1n = an1xi1 + … + annxin

Знайдіть стан процесу в момент часу M. Кожен параметр повинен бути порахованим за модулем 100007.

Вхідні дані

Перший рядок містить кількість тестів T (1T10). Перший рядок кожного тесту містить 2 числа: N, (1N100) – кількість параметрів і M (0M109) – момент часу. Далі йде N рядків, кожен з яких містить N цілих чисел, відокремлених пропусками. j-е число в i-й рядку – aij (0aij109). Далі йде один рядок, що містить N цілих чисел. j-е число в цьому рядку – x0j (0x0j109).

Вихідні дані

Виведіть T рядків вигляду "Case #A: xM1xMn", де A – номер тесту (починаючи з 1), xM1, …, xMn – шукані параметри для даного тесту.

Ліміт часу 15 секунд
Ліміт використання пам'яті 64 MiB
Вхідні дані
2
1 5
2
1
2 7
14 26
32 45
534 623
Вихідні дані
Case #1: 32
Case #2: 62813 87846