AT_npcapc_2024_n Product Matrix

给定一个 $N$ 阶正方矩阵 $P(x)$，其各元素均为一次多项式。$P(x)$ 的第 $(i, j)$ 项为 $a_{i,j} x + b_{i,j}$。 请计算 $\prod_{i=0}^{M-1} P(2^i x) = P(x) P(2x) \dots P(2^{M-1} x)$ 的第 $(1, 1)$ 项 $f(x) = \sum_{i=0}^{M} c_i x^i$ 的各个系数 $c_0, c_1, \dots, c_M$，并对 $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$ 每个系数，每个数输出为一行，并对 $10^9+7$ 取模，且 $c_i$ 要保证在 $0$ 到 $10^9+6$ 之间。

### 注意 本题的时间限制较为严格。 --- ### 样例解释 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$。 ### 数据范围 - $1 \leq N \leq 6$ - $1 \leq M \leq 5 \times 10^5$ - $0 \leq a_{i,j}, b_{i,j} < 10^9+7$ 由 ChatGPT 5 翻译