Problem #1125 - ECNU Online Judge

单点时限: 2.0 sec

内存限制: 256 MB

前面我们已经做了 $A^{B} mod C$ ，这里提高一下。相信大家也会轻松解决的。

$A$ 为一个方阵，则 $T r (A)$ 表示 $A$ 的迹（就是主对角线上各项的和），现要求 $T r (A^{k}) mod 9973$ 。

数据的第一行是一个 $T$ ，表示有 $T$ 组数据。

每组数据的第一行有 $n$ $(2 \leq n \leq 10)$ 和 $k$ $(2 \leq k < 10^{9})$ 两个数据。接下来有 $n$ 行，每行有 $n$ 个数据，每个数据的范围是 $[0, 9]$ ，表示方阵 $A$ 的内容。

对应每组数据，输出 $T r (A^{k}) mod 9973$ 。

Input

Output

2
2686

此题目用到了二分的思想，但是还需要了解矩阵相乘。

89 人解决，153 人已尝试。

122 份提交通过，共有 274 份提交。

3.9 EMB 奖励。

创建: 18 年前.

修改: 7 年，3 月前.

最后提交: 1 月，4 周前.

1125. Tr A