【模板】矩阵快速幂

题目背景

矩阵快速幂

题目描述

给定 $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$ 取模。

输入输出样例

输入样例 #1

2 1
1 1
1 1

输出样例 #1

1 1
1 1

说明

【数据范围】 对于 $100\%$ 的数据:$1\le n \le 100$,$0 \le k \le 10^{12}$, $|A_{i,j}| \le 1000 $