Prosesin simulyasiyası

Sizə hər hansı diskret təkamül prosesi verilmişdir. Prosesin hər vaxt anındakı vəziyyəti x₁, …, 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ⁱ⁺¹₁ = a₁₁xⁱ₁ + … + a_1nxⁱ_n

…

xⁱ⁺¹_n = a_n1xⁱ₁ + … + a_nnxⁱ_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⁹) –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⁹)-dir. Daha sonra N tam ədəd yerləşən bir sətir gəlir. Bu sətirdəki j-cu ədəd x⁰_j (0 ≤ x⁰_j ≤ 10⁹)-dur.

Çıxış verilənləri:

T sayda sətrin hər birini "Case #A: x^M₁ … x^M_n" şəklində verin. Burada A testin nömrəsidir(1-dən başlayaraq), x^M₁, …, x^M_n isə verilmiş test üçün axtarılan parametrlərdir.