题目描述

给定矩阵 $M$，请计算 $M^n$，并将其中每一个元素对 $1000000007$ 取模输出。

输入格式

第一行包含两个整数 $n,k$，其中 $n$ 使用二进制表示，可能含有前导零，$k \le 50$，$n \le 2^{10000}$。

余下 $k$ 行描述了一个 $k \times k$ 的矩阵 $M$。

输出格式

$k$ 行输出答案矩阵。

010 3
5 9 5
5 4 0
8 8 8

110 121 65
45 61 25
144 168 104