题目背景

请注意：本题不是矩阵快速幂模板题。

题目描述

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

输入格式

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

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

输出格式

输出题目描述中要求的矩阵，格式同输入。

输入输出样例 #1

输入 #1

010 3
5 9 5
5 4 0
8 8 8

输出 #1

110 121 65
45 61 25
144 168 104

说明/提示

对于 $100\%$ 的数据，$1\leq n\leq 2^{10^4}$，$1\leq k\leq 50$，$0\leq M_{i,j}<10^9+7$。