题目描述

给定正整数 $m$ 和严格递增的非负整数序列

令

给定非负整数 $c$ 和 $c$ 个整数 $A_1,A_2,\ldots,A_c$，令集合

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

• 这 $n$ 个整数的按位异或和为 $0$；
• 对于每个在方案中出现过的整数，它的出现次数属于集合 $A$。

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

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

输入格式

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

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

最后一行输入 $m$ 个非负整数 $a_1,a_2,\ldots,a_m$。

输出格式

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

样例 1

样例输入 1

4 3 0
1 3 5

样例输出 1

1978

样例 2

样例输入 2

3 5 1
2
0 1 2 5 6

样例输出 2

1494

样例 3

样例输入 3

2333 2 0
114514 1919810

样例输出 3

996160481

样例 4

样例输入 4

2333 2 5
2 3 4 5 6
114514 1919810

样例输出 4

264224065

数据范围与约定

对于全部数据：