시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 18 5 3 37.500%

문제

크기가 $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$

예제 입력 1

1 0 2 4
1

예제 출력 1

33

예제 입력 2

2 3 4 5
1 0
0 1

예제 출력 2

33552 0
0 33552

예제 입력 3

3 23 45 107
5 7 2
1 8 9
3 4 5

예제 출력 3

601338635 934201293 356700741
960409891 125261415 197093893
136328022 287118456 122438416