eolymp
Competitions

ADA University - January 30

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