Matrix and Fibonacci Sum

You are given a $K \times K$ matrix $M$ and nonnegative integers $N$, $a$, and $d$. Let $M_{r,c}$ denote the entry in row $r$ and column $c$ of $M$.

Define the matrix $S$ as follows.

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

Here, $M^0$ is the identity matrix. The Fibonacci numbers are defined by $F_0 = 0$, $F_1 = 1$, and, for $i > 1$, $F_i = F_{i-1} + F_{i-2}$.

Compute the matrix $S$.

The first line contains $K$, $a$, $d$, and $N$.

The next $K$ lines contain the entries of matrix $M$. The $i$-th of these lines contains $M_{i,1}$, $M_{i,2}$, ..., $M_{i,K}$, separated by spaces.

Print $K$ lines containing the entries of matrix $S$ modulo $998244353$.

On the $i$-th line, print $S_{i,1}$, $S_{i,2}$, ..., $S_{i,K}$ separated by spaces.

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