[AdditionalFile6018.zip](file://AdditionalFile6018.zip?type=additional_file)

#6018. Shlw loves matrix II

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

给定矩阵 $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}$