Stage Light Transformation

You are given a square background screen consisting of an n×n grid. The rows are numbered from 1 to n from left to right and the columns from 1 to n from top to bottom. The light at row r and column c is denoted by (r, c).

Two strictly increasing integer sequences of length m are given: \(\{x_i\}_{i=1}^{m}\) and \(\{y_i\}_{i=1}^{m}\), satisfying \[ 0\le x_1,\,y_1 \quad\text{and}\quad x_m,y_m\le n. \]

The program performs a light transformation operation k times. In each operation, four integers \(i_1,i_2,j_1,j_2\) are chosen uniformly at random subject to \[ 1\le i_1 < i_2 \le m,\quad 1\le j_1 < j_2 \le m. \] Then, every light 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})\) has its state toggled (i.e. XOR with 1; on becomes off, off becomes on).

Initially, all lights are off (value 0). After k operations the expected number of lights on is computed. Since the answer may be fractional, output it modulo \(998244353\) (that is, output the unique integer x with \(0\le x<998244353\) such that the answer is congruent to x modulo \(998244353\)).

Simplified Problem Statement:

You are given an n×n matrix initialized with zeros. Two increasing sequences \(\{x_i\}\) and \(\{y_i\}\) of length m are provided, with \[ 0\le x_1,\,y_1 \quad\text{and}\quad x_m,y_m\le n. \] One operation is defined as follows:

• Randomly select four indices \(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\).
• Toggles 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})\) (i.e. each element is XORed with 1).

After performing k operations independently, compute the expected sum of the matrix (i.e. the expected number of ones). Print the answer modulo \(998244353\).

inputFormat

The first line contains three integers n, m and k (1 ≤ n ≤ 1000, 2 ≤ m ≤ 1000, 1 ≤ k ≤ 109).

The second line contains m integers \(x_1,x_2,\dots,x_m\) in strictly increasing order (with \(0\le x_1< x_2< \cdots < x_m\le n\)).

The third line contains m integers \(y_1,y_2,\dots,y_m\) in strictly increasing order (with \(0\le y_1< y_2< \cdots < y_m\le n\)).

outputFormat

Output a single integer — the expected number of lights on after k operations, taken modulo \(998244353\).

sample

5 3 1
0 2 5
0 3 5

443664756