#P1458. 【模板】矩阵快速幂

【模板】矩阵快速幂

Background

矩阵快速幂

Description

给定 n×nn \times n 的矩阵 A,求 AkA^k

Format

Input

第一行两个整数 n,k 接下来 n 行,每行 n 个整数,第 i 行的第 j 的数表示 Ai,jA_{i,j}

Output

输出 AkA^k

nn 行,每行 nn 个数,第ii 行第 jj 个数表示 (Ak)i,j(A^k)_{i,j}​,每个元素对 109+710^9+7 取模。

Samples

2 1
1 1
1 1
1 1
1 1

Limitation

对于 100%100\%的数据:1n1001\le n \le 1000k10120 \le k \le 10^{12},Ai,j1000 |A_{i,j}| \le 1000