题目描述

给定 $m$ 和序列 $a_1, a_2, \dots, a_m$，令 $R = 2^{a_1} + 2^{a_2} + \dots + 2^{a_m}$，保证 $a_1 < a_2 < \dots < a_m$。

给定 $c$ 和 $c$ 个整数 $A_1, A_2, \dots, A_c$，令集合 $A = \{1, A_1, A_2, \dots, A_c\}$。

你需要选取 $n$ 个 $[0, R)$ 中的整数，使得：

• 其异或和为 $0$。
• 对于每个出现过的整数，其出现次数 $\in A$。

两种方案不同，当且仅当存在某个整数出现次数不同。

求出方案数取模 $998244353$ 的结果。

输入格式

第一行，三个整数 $n, m, c$。

第二行，$c$ 个正整数 $A_1, A_2, \dots, A_c$。若 $c=0$ 则没有这一行。

第 $[c > 0]+1$ 行，$m$ 个非负整数 $a_1, a_2, \dots, a_m$。

输出格式

一行，一个非负整数表示答案。

样例

样例输入 1

4 3 0
1 3 5

样例输出 1

1978

样例输入 2

3 5 1
2
0 1 2 5 6

样例输出 2

1494

样例输入 3

2333 2 5
2 3 4 5 6
114514 1919810

样例输出 3

264224065

数据范围

对于 $100\%$ 的数据，$1 \le n, m \le 10^5$，$0 \le c \le 10$，$0 \le a_1 < a_2 < \dots < a_m \le 10^{18}$，$1 < A_1 < A_2 < \dots < A_c \le n$。

各测试点数据范围如下表：