#6018. Shlw loves matrix II

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: l0nl1f3

题目描述

给定矩阵 M ,请计算 M^n ,并将其中每一个元素对 1000000007 取模输出。

输入格式

第一行包含两个整数 n,k ,其中 n 使用二进制表示,可能含有前导零

余下 k 行描述了一个 k \times k 的矩阵 M

输出格式

k 行输出答案矩阵

样例

输入样例

010 3
5 9 5
5 4 0
8 8 8

输出样例

110 121 65
45 61 25
144 168 104

数据范围与提示

k\leq 50,n\leq 2^{10000}