49 - 矩阵快速幂

已知一个n*n的矩阵A,矩阵B = (A^k)\%4399,你能求出矩阵B的主对角线各项的和吗?

输入

第一行输入两个正整数n,k 
接下来n行,每行n个整数A_{ij},对应着矩阵(i,j)位置上的值。 

输出

输出矩阵B的主对角线上各项的和,并对4399取模。 
 

样例

输入

2 2
1 0
0 1

输出

2

提示

【数据规模】 
2≤n≤10,2≤k<10^9,0≤Aij<10

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题