AT_npcapc_2024_n Product Matrix

各要素が $ 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 $ で求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 未満で出力せよ。

### 注意 この問題の TL は厳しめに設定されています。 --- ### Sample Explanation 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) = 14x^2 + 8x + 4 $ です。 ### Constraints - $ 1 \le N \le 6 $ - $ 1 \le M \le 5 \times 10^5 $ - $ 0 \le a_{i,j},b_{i,j} < 10^9 + 7 $