Problems
Matrix Power Series
Matrix Power Series
Given a n × n matrix A and a positive integer k, find the sum S = A + A^2
+ A^3
+ ... + A^k
.
Input data
The first line contains three positive integers n (n ≤ 30), k (k ≤ 10^9
) and m (m < 10^4
). Then follow n lines each containing n non-negative integers below 32768, giving A's elements in row-major order.
Output data
Print the elements of S modulo m in the same way as A is given.
Examples
Input example #1
2 2 4 0 1 1 1
Output example #1
1 2 2 3