Background

Note: This problem is not a matrix fast exponentiation template problem.

Problem Description

Given a matrix $M$, compute $M^n$, and output each element modulo $10^9+7$.

Input Format

The first line contains two integers $n, k$, where $n$ is given in binary and may contain leading zeros.

The next $k$ lines describe a $k \times k$ matrix $M$.

Output Format

Output the matrix required in the description, using the same format as the input.

010 3
5 9 5
5 4 0
8 8 8

110 121 65
45 61 25
144 168 104

Hint

For $100\%$ of the testdata, $1 \le n \le 2^{10^4}$, $1 \le k \le 50$, and $0 \le M_{i,j} < 10^9+7$.

Translated by ChatGPT 5