题目描述

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

输入格式

第一行包含两个整数 $n,k$，其中 $ n $ 使用二进制表示，可能含有前导零

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

输出格式

$k$ 行输出答案矩阵

样例

input

010 3
5 9 5
5 4 0
8 8 8

output

110 121 65
45 61 25
144 168 104

数据范围与提示

$k\leq 50,n\leq 2^{10000}$