Matrix and Fibonacci Sum

Time limit5sMemory limit512 MB

Summary

Compute the sum of Fibonacci numbers with linearly growing indices times increasing powers of a K×K matrix, modulo a prime, for N up to 10^1000.

Level: Hard9 of 10
Topics: Matrix, Math, Divide and conquer, Number theory
Solved: No attempts yet

Problem

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$ .

Input

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.

Output

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.

Constraints

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

Examples4

Example 1
Input
```
1 0 2 4
1
```
Expected output
```
33
```
Example 2
Input
```
2 3 4 5
1 0
0 1
```
Expected output
```
33552 0
0 33552
```

Example 3

Input

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

Expected output

601338635 934201293 356700741
960409891 125261415 197093893
136328022 287118456 122438416

Example 4

Input

2 1 1 10000000000
0 1
1 998244352

Expected output

697526667 332697837
332697837 364828830