2113번 - 행렬과 피보나치 수

크기가 $K \times K$인 행렬 $M$, 음이 아닌 정수 $N$, $a$, $d$가 입력으로 주어진다. 행렬 $M$의 $r$행 $c$열에 있는 원소는 $M_{r,c}$로 표시한다. 행렬 $S$는 다음과 같은 정의한다.

\[S = \sum_{i=0}^{N}{F_{a+i \cdot d} \cdot M^i} \text{.}\]

$M^0$는 단위 행렬이고, $F_0 = 0$, $F_1 = 1$, $i > 1$인 경우에는 $F_i = F_{i-1} + F_{i-2}$이다.

행렬 $S$를 구해보자.

첫째 줄에 $K$, $a$, $d$, $N$이 주어진다.

둘째 줄부터 $K$개의 줄에 행렬 $M$의 원소가 주어진다. 여기서 $i$번째 줄에 주어지는 값은 $M_{i,1}$, $M_{i,2}$, ..., $M_{i, K}$이고, 공백 한 칸으로 구분되어 있다.

총 K개의 줄에 행렬 $S$의 원소를 998,244,353으로 나눈 나머지를 출력한다. $i$번째 줄에 출력해야 하는 값은 $S_{i,1}$, $S_{i,2}$, ..., $S_{i, K}$를 998,244,353으로 나눈 나머지이고, 공백 한 칸으로 구분해야 한다.

• $1 \le K \le 100$
• $0 \le a, d \le 10^9$
• $0 \le N \le 10^{1000}$
• $0 \le M_{i,j} < 998244353$