#771. #6018. Shlw loves matrix II

#6018. Shlw loves matrix II

题目描述

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

输入格式

第一行包含两个整数 n,kn,k,其中 nn 使用二进制表示,可能含有前导零 余下 kk 行描述了一个 k×kk \times k 的矩阵 MM。

输出格式

kk 行输出答案矩阵

输入样例

010 3
5 9 5
5 4 0
8 8 8

输出样例

110 121 65
45 61 25
144 168 104

数据范围与提示

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