1382: #6018. Shlw loves matrix II

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

输入格式

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

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

输出格式

kkk 行输出答案矩阵

样例

输入样例

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}k50,n210000