행렬 점화식

Bobo가 새로운 행렬 수열 $M_0, M_1, \dots, M_n$을 다음과 같이 정의한다.

• $M_0 = A$
• $M_i = \left(\prod_{j = c_i}^{i - 1} M_j\right) \times B$

$m \times m$ 행렬 $A$, $B$와 정수 $c_1, c_2, \dots, c_n$이 주어진다. $\mathbb{Z}_{\mathrm{mod}}$에서 $M_n$을 구하라. 즉, 수의 덧셈과 곱셈은 모두 $\mathrm{mod}$로 나눈 나머지에서 계산한다.

입력은 0개 이상의 테스트 케이스로 이루어지며, 파일 끝(EOF)에서 끝난다. 각 테스트 케이스는 다음과 같다.

첫 줄에 세 정수 $n$, $m$, $\mathrm{mod}$가 주어진다 ($1 \leq n \leq 10^6$, $1 \leq m \leq 5$, $2 \leq \mathrm{mod} \leq 10^9$).

이어지는 $m$개 줄의 $i$번째 줄에는 $A_{i,1}, A_{i,2}, \dots, A_{i,m}$이 주어진다. 그다음 $m$개 줄의 $i$번째 줄에는 $B_{i,1}, B_{i,2}, \dots, B_{i,m}$이 주어진다 ($0 \leq A_{i,j}, B_{i,j} < \mathrm{mod}$).

마지막 줄에는 $n$개의 정수 $c_1, c_2, \dots, c_n$이 주어진다 ($0 \leq c_i < i$, $c_1 \leq c_2 \leq \dots \leq c_n$).

모든 테스트 케이스의 $n$을 합하면 $10^6$을 넘지 않는다.

각 테스트 케이스마다 $m$개 줄을 출력한다. $i$번째 줄에는 $C_{i,1}, C_{i,2}, \dots, C_{i,m}$을 출력한다. 여기서 $C_{i,j} = M_{n,i,j}$이다.