Description

For stage effects, lighting is an important role. The background screen is an $n \times n$ rectangle. Rows are numbered from left to right and columns are numbered from top to bottom as $1 \sim n$. A lighting cell at row $x$ and column $y$ is denoted by $(x,y)$.

As the dedicated lighting designer, A-Ling wrote a program to control the background lighting effects. She sets two increasing integer sequences $\{x_m\}$ and $\{y_m\}$ of length $m$, satisfying $0\le x_1,y_1$ and $x_m,y_m\le n$. Each time the lights change, the program uniformly randomly generates two pairs of integers $(i_1,i_2)$ and $(j_1,j_2)$, satisfying $1\le i_1<i_2\le m$ and $1\le j_1<j_2\le m$, and toggles (on becomes off, off becomes on) the state of all lighting cells $(r,c)$ that satisfy $x_{i_1}<r\le x_{i_2}$ and $y_{j_1}<c\le y_{j_2}$.

At the beginning of the performance, all lighting cells are off. After calculation, there will be a total of $k$ lighting changes by the end of the performance. Since the lighting effect at the curtain call is crucial, A-Ling wants to know: at the end, what is the expected number of lighting cells that are on?

Since the answer may be a decimal, to avoid precision loss, output the value of the answer modulo $998244353$.

Simplified Statement

There is an $n\times n$ matrix, with all elements initially equal to $0$. Given increasing sequences $\{x_m\}$ and $\{y_m\}$, where $0\le x_1,y_1$ and $x_m,y_m\le n$, one operation is defined as:

• Randomly choose four integers $i_1,i_2,j_1,j_2$ satisfying $1\le i_1<i_2\le m$ and $1\le j_1<j_2\le m$.
• XOR every element in the submatrix with top-left corner $(x_{i_1}+1,y_{j_1}+1)$ and bottom-right corner $(x_{i_2},y_{j_2})$ by $1$.

Find the expected value of the sum of all elements in the matrix after $k$ operations. Take the answer modulo $998244353$.

Input Format

The first line contains three integers $n,m,k$.

The second line contains $m$ integers, where the $i$-th number denotes $x_i$.

The third line contains $m$ integers, where the $i$-th number denotes $y_i$.

Output Format

Output one integer in one line, representing the value of the answer modulo $998244353$.

2 3 1
0 1 2
0 1 2

110916041

3 3 3
0 1 2
0 1 2

592921545

Hint

Sample Explanation 1

In the sample, $\{x_m\}=\{y_m\}=\{0,1,2\}$. You can see that any submatrix of this $2\times 2$ matrix can be toggled. When the submatrix sizes are $1,2,4$, the numbers of corresponding choices are $4,4,1$. Since there is only one operation, the corresponding final sums of matrix elements are $4\times 1,4\times 2,1\times 4$. Therefore, the answer is $\frac{4+8+4}{4+4+1}=\frac{16}9$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the data, $2\le m\le \min(n+1,10^3)$, $1\le n\le10^9$, $1\le k\le 10^6$. It is guaranteed that $x_i$ are pairwise distinct and strictly increasing, and $y_i$ are pairwise distinct and strictly increasing.

Translated by ChatGPT 5