Sum of matrix powers

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.

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.

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.