## 题目背景 矩阵快速幂 ## 题目描述 给定 $n\times n$ 的矩阵 $A$，求 $A^k$。 ## 输入格式 第一行两个整数 $n,k$ 接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行的第 $j$ 的数表示 $A_{i,j}$。 ## 输出格式 输出 $A^k$ 共 $n$ 行，每行 $n$ 个数，第 $i$ 行第 $j$ 个数表示 $(A^k)_{i,j}$，每个元素对 $10^9+7$ 取模。 ```input1 2 1 1 1 1 1 ``` ```output1 1 1 1 1 ``` ## 提示 【数据范围】 对于 $100\%$ 的数据：$1\le n \le 100$，$0 \le k \le 10^{12}$, $|A_{i,j}| \le 1000 $