Description

给定一个N阶矩阵A，输出A的M次幂（M是非负整数） 　　

例如： 　
A=$\begin{vmatrix} 1 & 2 \\ 3 & 4 \\ \end{vmatrix}​$
$A^2$=$\begin{vmatrix} 7 & 10 \\ 15 & 22\\ \end{vmatrix}$

Format

Input

第一行是一个正整数$N$、$M$（$1< =N< =30, 0< =M< =5$），表示矩阵$A$的阶数和要求的幂数 　　

    接下来 N行，每行N个绝对值不超过10的非负整数，描述矩阵A的值

Output

输出共$N$行，每行$N$个整数，表示$A$的$M$次幂所对应的矩阵。相邻的数之间用一个空格隔开。

Samples

2  2 
1  2 
3  4

7 10
15 22