luogu#P10775. BZOJ4162 shlw loves matrix II

BZOJ4162 shlw loves matrix II

题目背景

请注意:本题不是矩阵快速幂模板题。

题目描述

给定矩阵 MM,计算 MnM^n,并将其中每一个元素对 109+710^9+7 取模输出。

输入格式

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

接下来 kk 行描述了一个 k×kk\times k 的矩阵 MM

输出格式

输出题目描述中要求的矩阵,格式同输入。

010 3
5 9 5
5 4 0
8 8 8
110 121 65
45 61 25
144 168 104

提示

对于 100%100\% 的数据,1n21041\leq n\leq 2^{10^4}1k501\leq k\leq 500Mi,j<109+70\leq M_{i,j}<10^9+7