Description

Given a n n matrix A and a positive integer k, find the sum S = A + A^2 + A^3 + + A^k.

Input

There are several test cases,for each case: 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 nonnegative integers below 32,768, giving As elements in row-major order.

Output

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

Sample Input

2 2 4 0 1 1 1

Sample Output

1 2 2 3

Source

POJ Monthly--2007.06.03, Huang, Jinsong