【模板】矩阵快速幂

题目背景

矩阵快速幂

题目描述

给定n\*n的矩阵A,求A^k

输入输出格式

输入格式


第一行,n,k 第2至n+1行,每行n个数,第i+1行第j个数表示矩阵第i行第j列的元素

输出格式


输出A^k 共n行,每行n个数,第i行第j个数表示矩阵第i行第j列的元素,每个元素模10^9+7

输入输出样例

输入样例 #1

2 1
1 1
1 1

输出样例 #1

1 1
1 1

说明

n<=100, k<=10^12, |矩阵元素|<=1000 算法:矩阵快速幂