問題文

1 から N の順に番号がついた N 個のマスが一直線に並んでいます。このうち B_1, ..., B_K の K マスには障害物があり、入ることができません。

高橋君は今からマス 1 をスタートして、マス N へ向かおうとしています。

ただし、高橋君が行うことのできる移動方法には制限があります。1 回の移動では、高橋君がマス x にいるとき x + D_1, x + D_2, ..., x + D_M のいずれかのマスに限って移動することができます。

障害物のあるマスや、N 個のマス以外に跳ぶことはできません。

高橋君が 1 回の移動でマス x から マス y に移動するとき、次の条件を満たす最小の非負整数 i のコストがかかります。

• x + 1 以上 y 以下の整数のいずれも 2^i で割り切れない。

マスからマスへの移動を繰り返してマス 1 からマス N に到達する経路のコストは、各移動にかかるコストの和です。

有り得る全ての経路についてのコストの和を 998244353 で割ったあまりを求めてください。

制約

• 3 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N-2
• 1 \leq M \leq N-1
• 1 < B_1 < B_2 < \cdots < B_K < N
• 0 < D_1 < D_2 < \cdots < D_M < N
• 入力は全て整数である

入力例 1

3 1 2
2
1 2

出力例 1

2

可能な経路は マス 1 からマス 3 に 移動するもののみです。

条件を満たす最小の非負整数が 2 であることが次のように確かめられるため、マス 1 からマス 3 への移動のコストは 2 です。

• 2^1 = 2 では 2 が割り切れるため、1 は条件を満たさない。
• 2^2 = 4 では 2, 3 のいずれも割り切れないので、2 は条件を満たす。

よって、この経路のコストは 2 です。

入力例 2

4 1 3
3
1 2 3

出力例 2

8

可能な経路は以下の 2 通りがあります。

• マス 1 からマス 4 に 移動する。この経路のコストは 3 です。

• マス 1 からマス 2 に移動し、マス 2 からマス 4 に 移動する。この経路のコストは 2 + 3 = 5 です。

よって、全ての経路についてのコストの和は 8 です。

入力例 3

4 2 2
2 3
1 2

出力例 3

0

そもそも マス 4 にたどり着けないので、0 を出力してください。

入力例 4

10 2 4
2 7
1 2 3 9

出力例 4

301