#P4162. shlw loves matrix II

    ID: 3377 传统题 1000ms 512MiB 尝试: 344 已通过: 100 难度: 4 上传者: 标签>难度分类普及+/提高-线性代数与代数矩阵快速幂矩阵转置数论同余的加减乘运算CF1600Berlekamp-Massey 算法

shlw loves matrix II

Shlw loves matrix II

题目描述

给定一个 kk 阶方阵 MM 和正整数 nn,计算 MnM^n。将结果矩阵的每个元素对 109+710^9+7 取模。

输入格式

第一行是用二进制表示的 nn 和用十进制表示的 kk(1≤n≤21041\le n\le2^{10^4},1≤k≤501\le k\le50)。nn 的二进制表示允许有前导零。

接下来 kk 行,每行 kk 个十进制整数,按行给出矩阵 MM。每个元素 Mi,jM_{i,j} 满足 0≤Mi,j<109+70\le M_{i,j}<10^9+7。

输出格式

输出 kk 行,每行 kk 个用空格分隔的整数,依次表示结果矩阵各元素的非负余数。

样例 #1

样例输入 #1

010 3
5 9 5
5 4 0
8 8 8

样例输出 #1

110 121 65
45 61 25
144 168 104