题目大意：求由矩阵 A构成的矩阵 S = A + A^2 + A^3 + … + A^k。k的取值范围是：10^9数据很大，应该二分。

对于一个k来说，s(k) = (1+A^(k/2)) *( A+A^2+……+A^(k/2))。如果k为奇数的话需要加上A^(k/2 + 1)。

所以二分求和，复杂度就降下来了，当然还得用到矩阵快速幂。

Description

Given a n × n matrix A and a positive integer k, find the sum S = A + A² + A³ + … + A^k.

Input

The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 10⁹) and m (m < 10⁴). Then follow n lines each containing nnonnegative integers below 32,768, giving A’s 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

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include