Competitions

# Matrix Power Series

Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + ... + Ak.

#### Input

The first line contains three positive integers n (n30), k (k109) and m (m < 104). Then follow n lines each containing n non-negative integers below 32768, giving A's elements in row-major order.

#### Output

Print the elements of S modulo m in the same way as A is given.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2 2 4
0 1
1 1

Output example #1
1 2
2 3