12987번 - Matrix Again

문제

N * N 행렬 A와 정수 K, M이 주어졌습니다. 이때 A^k한 원소들을 M으로 나눈 나머지 값들을 구하는 것은 너무 쉬운 일입니다.

이제는 조금 다른 문제를 풀어보려 합니다.

S = A + A² + A³ + ... + A^K인 행렬 S가 있습니다. 행렬 S의 원소들을 M 으로 나눈 나머지 값들을 출력하세요.

입력

첫 번째 줄에 N, K, M (1 ≤ N ≤ 50, 1 ≤ K ≤ 10⁹, 1 ≤ M ≤ 10⁴) 이 공백을 구분으로 주어집니다.

다음 N개의 줄에 걸쳐 행렬 A가 주어집니다. (-10⁴ ≤ A_ij ≤ 10⁴, 1 ≤ i, j ≤ N)

출력

수열 S의 각 원소들을 M으로 나눈 나머지 값들을 출력하세요.

제한

힌트

나머지 연산의 결과는 0 또는 양수이어야 한다.