#P16727. 异或和

异或和

题目描述

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

a1,a2,…,am,a_1,a_2,\ldots,a_m,

令

R=2a1+2a2+⋯+2am。R=2^{a_1}+2^{a_2}+\cdots+2^{a_m}。

给定非负整数 cc 和 cc 个整数 A1,A2,…,AcA_1,A_2,\ldots,A_c,令集合

A={1,A1,A2,…,Ac}。A=\{1,A_1,A_2,\ldots,A_c\}。

你需要选取 nn 个属于 [0,R)[0,R) 的整数,使得:

  • 这 nn 个整数的按位异或和为 00;
  • 对于每个在方案中出现过的整数,它的出现次数属于集合 AA。

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

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

输入格式

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

若 c>0c>0,第二行输入 cc 个正整数 A1,A2,…,AcA_1,A_2,\ldots,A_c;若 c=0c=0,则没有这一行。

最后一行输入 mm 个非负整数 a1,a2,…,ama_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

数据范围与约定

对于全部数据:

1≤n,m≤105,1\le n,m\le 10^5, 0≤c≤10,0\le c\le10, 0≤a1<a2<⋯<am≤1018,0\le a_1<a_2<\cdots<a_m\le10^{18}, 1<A1<A2<⋯<Ac≤n。1<A_1<A_2<\cdots<A_c\le n。
测试点编号 特殊限制
11 n≤3, am≤6n\le3,\ a_m\le6
2∼32\sim3 c=0, m≤1c=0,\ m\le1
4∼64\sim6 c=0, n≤7, m≤100c=0,\ n\le7,\ m\le100
7∼97\sim9 c=0, n≤10, m≤100c=0,\ n\le10,\ m\le100
10∼1210\sim12 c=0, n,m≤100c=0,\ n,m\le100
13∼1513\sim15 c=0, n,m≤5000c=0,\ n,m\le5000
16∼1816\sim18 c=0c=0
19∼2019\sim20 无特殊限制