#6728. U 群把妹王

题目描述

• 小天使 忆艾 ●：哇哦，你一个人在 UOJ 群找什么呢？ 「1. 找多项式」 「2. 找小天使」

有 $n \times m$ 个格子，每个格进行染色，可以选择 $k$ 种颜色之一。对于集合 $S, T$，你需要计数有多少种格子的染色方案，满足：

• 对于每一行的图案拿出来，和它相同的图案总共有 $r$ 行（含自身），则 $r \in S$。
• 对于每一列的图案拿出来，和它相同的图案总共有 $c$ 列（含自身），则 $c \in T$。

答案对 $P = 998244353$ 取模。

为了让这道题看起来代码比较健康，保证 $1 \in S \cap T$。

输入格式

第一行输入五个正整数，分别为 $n, m, k, a, b$。

接下来一行输入 $a$ 个正整数，从小到大表示集合 $S$ 中的数，保证数不重复。

接下来一行输入 $b$ 个正整数，从小到大表示集合 $T$ 中的数，保证数不重复。

输出格式

输出一个整数，表示满足要求的染色数同余 $P$。

样例 1

输入

2 2 2 1 1
1
1

输出

10

即任意两行颜色不同，任意两列颜色不同。

$2^4 = 16$ 种染色方案中，有以下 6 种是不合法的：

LibreOJ

样例 2

输入

49 50 666 5 4
1 2 6 9 19
1 2 3 5

输出

132764272

样例 3

输入

10492 11451 1122334 5 5
1 2 600 9700 10492
1 2 301 3131 4921

输出

208881352

数据范围与提示

对于 10% 的数据，保证 $n, m \leq 50$。

对于 40% 的数据，保证 $n, m \leq 3000$。

对于另外 10% 的数据，保证 $S = T = \{1\}$。

对于 100% 的数据，保证 $1 \leq n, m \leq 10^5, 1 \leq k \leq P - 1, 1 \leq a, b \leq 5, 1 \in S \cap T, S \subseteq [1, n], T \subseteq [1, m]$。