Prosesin simulyasiyası
Sizə hər hansı diskret təkamül prosesi verilmişdir. Prosesin hər vaxt anındakı vəziyyəti x_1, …, x_n parametrləri ilə təsvir olunur. Təkamülün hər vaxt anındakı vəziyyəti aşağıdakı xətti tənliklər sistemi vasitəsilə təsvir olunur:
x^{i+1}_1 = a_11x^i_1 + … + a_1nx^i_n
…
x^{i+1}_n = a_n1x^i_1 + … + a_nnx^i_n
Prosesin M vaxt anındakı vəziyyətini tapın. Hər bir parametr modulca 100007-yə qədər hesaba alınmalıdır.
Giriş verilənləri
Girişin birinci sətrində T (1 ≤ T ≤100) testlərin sayı yerləşir. Hər bir testin birinci sətrində iki ədəd yerləşir: N, (1 ≤ N ≤ 100) –parametrlərin sayı və M (0 ≤ M ≤ 10^9) –vaxt anı. Sonra hər birində aralarında boşluq işarəsi olmaqla N ədəd yerləşən N sətir gəlir. i-ci sətirdəki j-cu ədəd a_ij (0 ≤ a_ij ≤ 10^9)-dir. Daha sonra N tam ədəd yerləşən bir sətir gəlir. Bu sətirdəki j-cu ədəd x^0_j (0 ≤ x^0_j ≤ 10^9)-dur.
Çıxış verilənləri
T sayda sətrin hər birini "Case #A: x^M_1 … x^M_n" şəklində verin. Burada A testin nömrəsidir(1-dən başlayaraq), x^M_1, …, x^M_n isə verilmiş test üçün axtarılan parametrlərdir.