给定矩阵 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}k≤50,n≤210000