题目背景

  「为了你唱下去——直到荒芜」

  「为了你唱下去——直到……」

  舞台上，享受地阖上眼眸，双手交叠扣在话筒，后脚踮起，在随着节奏闪烁变换的灯光下轻摇……

  嘴角轻扬，绫珍惜着步入瞳孔的每一粒光，那些从天依的发丝、脸颊划过的，带着属于她的旖旎，轰击着明明做好防备的绫的心尖。

  收尾的音调扬起，灯光，也是那样应景呢。

题目描述

对于舞台效果，灯光是重要的角色。背景屏幕是一个 $n \times n$ 的矩形，行从左到右，列从上到下编号为 $1\sim n$，并用 $(x,y)$ 表示第 $x$ 行第 $y$ 列的灯光单元。

作为御用灯光师的阿绫设计了一个控制背景灯光效果的程序。她设定了两个长度为 $m$ 的递增整数序列 $\{x_m\}$ 和 $\{y_m\}$，且满足 $0\le x_1,y_1$，$x_m,y_m\le n$。每次灯光变换，程序会均匀地随机生成两对整数 $(i_1,i_2),(j_1,j_2)$，满足 $1\le i_1<i_2\le m$，$1\le j_1<j_2\le m$，转换满足 $x_{i_1}<r\le x_{i_2}$，$y_{j_1}<c\le y_{j_2}$ 的所有灯光单元 $(r,c)$ 的状态（亮变为熄，熄变为亮）。

表演开始时，所有灯光单元处于熄灭状态；经计算，到表演结束时，一共会发生 $k$ 次灯光变换。而表演落幕时的灯光效果极为关键，所以阿绫想知道，表演落幕时，期望有多少个灯光单元是亮着的？

由于答案可能是一个小数，为了避免损失精度，请输出答案在 $998244353$ 模意义下的值。

简化题意

有一个 $n\times n$ 的矩阵，初始所有元素的值为 $0$。给出递增序列 $\{x_m\}$ 和 $\{y_m\}$，其中 $0\le x_1,y_1$，$x_m,y_m\le n$，一次操作定义为：

• 随机选出四个整数 $i_1,i_2,j_1,j_2$，满足 $1\le i_1<i_2\le m$，$1\le j_1<j_2\le m$。
• 把以 $(x_{i_1}+1,y_{j_1}+1)$ 为左上角，$(x_{i_2},y_{j_2})$ 为右下角的子矩阵的每个元素异或 $1$。

求 $k$ 次操作后矩阵内元素之和的期望值。答案对 $998244353$ 取模。

输入格式

第一行三个整数，分别为 $n,m,k$ 。

第二行 $m$ 个整数，其中第 $i$ 个数表示 $x_i$ 。

第三行 $m$ 个整数，其中第 $i$ 个数表示 $y_i$ 。

输出格式

一行一个整数，表示答案在 $998244353$ 模意义下的值。

2 3 1
0 1 2
0 1 2

110916041

3 3 3
0 1 2
0 1 2

592921545

提示

样例解释 1

样例中，$\{x_m\}=\{y_m\}=\{0,1,2\}$。可以发现，此 $2\times 2$ 矩阵的任意一个子矩阵都可以被变换。当子矩阵大小分别为 $1,2,4$ 时，对应方案数分别为 $4,4,1$，由于只操作一次，所以对应的最终矩阵元素之和分别为 $4\times1,4\times2,1\times 4$。于是，答案为 $\frac{4+8+4}{4+4+1}=\frac{16}9$。

数据规模与约定

本题采用捆绑测试。

对于 $100\%$ 的数据，$2\le m\le \min(n+1,10^3)$，$1\le n\le10^9$，$1\le k\le 10^6$，保证 $x_i$ 互不相等且递增，$y_i$ 互不相等且递增。