Q. Counting Grids Again
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a rectangular grid (0-indexed) $$$A$$$ with $$$N$$$ rows and $$$M$$$ columns, in which $$$A_{i, j} \gt A_{i + 1, j}$$$ and $$$A_{i, j} \gt A_{i, j + 1}$$$. Consider an undirected graph with $$$(NM)^K$$$ vertices represented as a tuple $$$(P_1, P_2, \dots, P_K)$$$, where $$$P_x$$$ represents some position $$$(i, j)$$$ $$$(0 \leq i \lt N, 0 \leq j \lt M)$$$. Vertices $$$(P_1, P_2, \dots, P_K)$$$ and $$$(Q_1, Q_2, \dots, Q_K)$$$ are connected by an edge if the following two conditions are satisfied:

  • There is exactly one index $$$x$$$ where $$$P_x \neq Q_x$$$.
  • $$$P_x$$$ and $$$Q_x$$$ differ in either the $$$i$$$ coordinate or the $$$j$$$ coordinate but NOT both.
The weight of each vertex $$$(P_1, P_2, \dots, P_K)$$$ is $$$(NM)^{K \cdot S}$$$, where $$$$$$S = \sum_{x=1}^K A_{P_x}$$$$$$ Find the maximum total weight of the vertices in an independent set of the graph modulo $$$998244353$$$.
Input

The first line contains $$$3$$$ positive integers $$$N$$$, $$$M$$$, and $$$K$$$ $$$(1 \leq NM \leq 4 \cdot 10^6, 1 \leq K \leq 10^9)$$$.

The next $$$N$$$ lines contain $$$M$$$ integers representing $$$A_{i, j}$$$ $$$(0\leq A_{i, j} \leq 10^9, A_{i, j} \gt A_{i + 1, j}, A_{i, j} \gt A_{i, j + 1})$$$.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Test $$$1$$$ satisfies $$$K = 1$$$.

Tests $$$2-4$$$ satisfy $$$N, M \leq 20, K \leq 3$$$.

Tests $$$5-12$$$ satisfy $$$N, M \leq 300$$$.

Tests $$$13-15$$$ satisfy $$$N, M \leq 2000$$$.

Tests $$$16-17$$$ satisfy $$$NM \leq 2 \cdot 10^5$$$.

Tests $$$18-20$$$ satisfy no additional constraints.

Output

Output $$$1$$$ integer, the maximum total weight of the vertices in an independent set of the graph modulo $$$998244353$$$.

Examples
Input
2 2 1
2 1
1 0
Output
17
Input
2 2 2
2 1
1 0
Output
67073
Input
3 3 3
4 3 2
3 2 1
2 1 0
Output
189222073
Note

—

Problem Idea: HaccerKat

Problem Preparation: HaccerKat

Occurrences: Advanced M