eolymp
bolt
Try our new interface for solving problems
Problems

Matrix Power Series

Matrix Power Series

Time limit 1 second
Memory limit 128 MiB

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 (n30), k (k10^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