#P18189. Product Matrix

Product Matrix

Product Matrix

题目描述

给定两个 N×NN\times N 矩阵 A=(ai,j)A=(a_{i,j})、B=(bi,j)B=(b_{i,j}),定义矩阵多项式

P(x)=Ax+B.P(x)=Ax+B.

也就是说,P(x)P(x) 的第 ii 行第 jj 列元素为 ai,jx+bi,ja_{i,j}x+b_{i,j}。每个元素的次数至多为 11,允许常数多项式及零多项式。

按照下列顺序进行矩阵乘法:

R(x)=P(x)P(2x)⋯P(2M−1x).R(x)=P(x)P(2x)\cdots P(2^{M-1}x).

设 R(x)R(x) 的第 11 行第 11 列元素为

f(x)=∑k=0Mckxk.f(x)=\sum_{k=0}^{M}c_kx^k.

求 c0,c1,…,cMc_0,c_1,\ldots,c_M 对 109+710^9+7 取模后的值。注意矩阵乘法的顺序固定,不能任意交换因子。

输入格式

第一行包含两个整数 N,MN,M。

接下来 NN 行,每行 NN 个整数,给出矩阵 AA 的各行。

再接下来 NN 行,每行 NN 个整数,给出矩阵 BB 的各行。

输出格式

输出 M+1M+1 行,第 k+1k+1 行输出 ckc_k 对 109+710^9+7 取模后的值,范围为 [0,109+6][0,10^9+6]。

即使实际次数小于 MM,也必须输出全部 M+1M+1 个系数。

数据范围

  • 1≤N≤61\le N\le6;
  • 1≤M≤5×1051\le M\le5\times10^5;
  • 0≤ai,j,bi,j<109+70\le a_{i,j},b_{i,j}<10^9+7。

输入只有一组数据。不保证任何矩阵可逆。

样例 1

输入:

2 2
1 2
3 4
2 0
1 2

输出:

4
8
14

样例 2

输入:

4 10
520471651 866160932 848899741 650346545
756377215 402412491 920748640 255249004
371442152 93295238 350011159 679848583
528399020 957465601 22001245 407745834
363922864 418156995 324388560 611306817
671914474 323815171 638034305 796072406
765823638 254662378 175686978 123364350
786531344 396717902 774813609 895184869

输出:

890467395
623743197
432365684
555543126
145580696
550546744
959254454
836036617
945090197
106843161
866547396

样例 3

输入:

6 23
101670804 457970042 521121852 851881468 298366530 271962368
881900040 161849089 409608300 527884448 898980182 538728808
624037110 955334452 644656371 684645088 612630196 365375437
135489465 838789241 374389562 238291227 977400760 496900790
921432977 606711088 740916866 405856539 822796504 19906274
631056816 823924205 719574385 332547421 298321832 594473309
145245098 519214077 131200957 702537460 682007417 304700059
419152148 943797679 19640790 464034522 441355576 454665900
822982080 991406863 249537771 45708817 502700323 683669766
326512291 871373558 410675396 208947517 645163777 622674739
606534945 349193474 895660493 579299011 661372605 314032169
497618687 102217570 426720147 363888279 910628723 894753922

输出:

18827363
93291123
549166310
727345493
212460686
835043567
382235992
234331494
126083178
340949995
361327462
549134620
481914498
34075195
89718312
945811332
898724999
944812555
123616792
779724718
995912550
188150326
361531843
801483934

样例 1 解释

$$P(x)P(2x)= \begin{pmatrix}x+2&2x\\3x+1&4x+2\end{pmatrix} \begin{pmatrix}2x+2&4x\\6x+1&8x+2\end{pmatrix} = \begin{pmatrix} 14x^2+8x+4&20x^2+12x\\ 30x^2+24x+4&44x^2+28x+4 \end{pmatrix}.$$

因此 f(x)=14x2+8x+4f(x)=14x^2+8x+4,依次输出 4,8,144,8,14。