Sum of matrix powers

Time limit2sMemory limit512 MB

Summary

Compute A + A^2 + ... + A^B for an N by N matrix A, with B up to 1e11, printing every entry modulo 1000.

Level: Medium7 of 10
Topics: Divide and conquer, Matrix, Recursion
Solved: No attempts yet

Problem

You are given an $N \times N$ matrix $A$ . Write a program that computes the matrix obtained by adding every power of $A$ from the first up to the $B$ th:

$S = A^1 + A^2 + \cdots + A^B$

The entries can grow very large, so print each entry of $S$ modulo 1,000.

Input

The first line contains the matrix size $N$ and the exponent bound $B$ , separated by a space. ( $2 \le N \le 5$ , $1 \le B \le 100{,}000{,}000{,}000$ )

Each of the next $N$ lines contains $N$ entries of $A$ , separated by spaces. Every entry is 0 or a natural number at most 1,000.

Output

Print the matrix $S$ on $N$ lines. Line $i$ contains the $N$ entries of row $i$ of $S$ , each taken modulo 1,000 and separated by a space.

Examples3

Example 1
Input
```
2 5
1 2
3 4
```
Expected output
```
313 914
871 184
```

Example 2

Input

Expected output

499 614 729
132 391 650
765 168 571

Example 3

Input

Expected output

23 0 0 0 23
23 0 0 0 23
23 0 0 0 23
23 0 0 0 23
23 0 0 0 23