N - Product Matrix
Editorial
/ 
/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 100 点
注意
この問題の TL は厳しめに設定されています。
問題文
各要素が 1 次の多項式である N 次正方行列 P(x) が与えられます。P(x) の (i,j) 成分は a_{i,j} x + b_{i,j} です。
\prod_{i=0}^{M-1} P(2^ix) = P(x) P(2x) \dots P(2^{M-1}x) の (1,1) 成分 f(x) = \sum_{i=0}^{M} c_ix^i の各係数 c_0,c_1,\dots,c_M を \bmod\ 10^9 + 7 で求めてください。
制約
- 1 \le N \le 6
- 1 \le M \le 5 \times 10^5
- 0 \le a_{i,j},b_{i,j} < 10^9 + 7
入力
入力は以下の形式で標準入力から与えられる。
N M
a_{1,1} a_{1,2} \dots a_{1,N}
a_{2,1} a_{2,2} \dots a_{2,N}
\vdots
a_{N,1} a_{N,2} \dots a_{N,N}
b_{1,1} b_{1,2} \dots b_{1,N}
b_{2,1} b_{2,2} \dots b_{2,N}
\vdots
b_{N,1} b_{N,2} \dots b_{N,N}
出力
c_0,c_1,\dots,c_M を \bmod\ 10^9 + 7 でこの順に改行区切りで出力せよ。なお、c_i は 0 以上 10^9 + 7 未満で出力せよ。
入力例 1
2 2 1 2 3 4 2 0 1 2
出力例 1
4 8 14
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) = 14x^2 + 8x + 4 です。
入力例 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
出力例 2
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
出力例 3
18827363 93291123 549166310 727345493 212460686 835043567 382235992 234331494 126083178 340949995 361327462 549134620 481914498 34075195 89718312 945811332 898724999 944812555 123616792 779724718 995912550 188150326 361531843 801483934