P7245 Lighting Effects

  "Sing for you—until everything becomes desolate."   "Sing for you—until..."   On the stage, she closes her eyes in enjoyment, hands clasped around the microphone, standing on tiptoe with her back foot, gently swaying under the lights that flicker and change with the rhythm...   With a slight smile, Ling cherishes every ray of light that enters her eyes. Those traces of beauty that sweep across Tianyi's hair and cheeks, carrying something that belongs only to her, strike at the very tip of Ling's heart even though she has already prepared herself.   As the ending note rises, the lights also match the moment so well.

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

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 one integer in one line, representing the value of the answer modulo $998244353$.

#### 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. | Subtask | Score | $n$ | $m$ | $k$ | | :----: | :--: | :----------: | :------: | :----------: | | 1 | 10 | $ \le 4$ | $ \le 3$ | $ \le 2$ | | 2 | 5 | / | $2$ | / | | 3 | 25 | $ \le 10^2 $ | / | $ \le 10^2 $ | | 4 | 20 | $ \le 10^9 $ | / | $ \le 10^2 $ | | 5 | 20 | $ \le 10^2 $ | / | $ \le 10^6 $ | | 6 | 20 | / | / | / | Translated by ChatGPT 5