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

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

对应每组数据，输出 Tr($A^k$)%9973。