P10775 BZOJ4162 shlw loves matrix II

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

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

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 the matrix required in the description, using the same format as the input.

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