Problem11337--[yosupo] Linear Algebra - Matrix Product

11337: [yosupo] Linear Algebra - Matrix Product

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

Given $N \times M$ matrix $A$ and $M \times K$ matrix $B$, print $C = AB \bmod 998244353$.

Input

$N\ M\ K$
$a_{11}$ $a_{12}$ ... $a_{1M}$
$a_{21}$ $a_{22}$ ... $a_{2M}$
:
$a_{N1}$ $a_{N2}$ ... $a_{NM}$
$b_{11}$ $b_{12}$ ... $b_{1K}$
$b_{21}$ $b_{22}$ ... $b_{2K}$
:
$b_{M1}$ $b_{M2}$ ... $b_{MK}$

Output

$c_{11}$ $c_{12}$ ... $c_{1K}$
$c_{21}$ $c_{22}$ ... $c_{2K}$
:
$c_{N1}$ $c_{N2}$ ... $c_{NK}$

Constraints

- $1 \leq N,M,K \leq 2^{10}$
- $0 \leq a_{ij},b_{ij} < 998244353$

Sample 1 Input

2 2 2
1 1
1 0
5 2
3 1

Sample 1 Output

8 3
5 2

Sample 2 Input

1 2 3
1 2
3 4 5
6 7 8

Sample 2 Output

15 18 21

Sample 3 Input

1 1 1
123456
789012

Sample 3 Output

578563231

HINT

Source/Category