Given $m$ and a sequence $a_1, a_2, \dots, a_m$, let $R = 2^{a_1} + 2^{a_2} + \dots + 2^{a_m}$, where it is guaranteed that $a_1 < a_2 < \dots < a_m$.

Given $c$ and $c$ integers $A_1, A_2, \dots, A_c$, let the set $A = \{1, A_1, A_2, \dots, A_c\}$.

You need to choose $n$ integers in the range $[0, R)$ such that:

• Their XOR sum is $0$.
• For every integer that appears in the selection, its frequency of occurrence is in $A$.

Two schemes are considered different if and only if there exists at least one integer whose frequency of occurrence is different.

Calculate the number of such schemes modulo $998244353$.

Input

The first line contains three integers $n, m, c$.

The second line contains $c$ positive integers $A_1, A_2, \dots, A_c$. If $c=0$, this line does not exist.

The $[c > 0]+1$-th line contains $m$ non-negative integers $a_1, a_2, \dots, a_m$.

Output

A single line containing a non-negative integer representing the answer.

Examples

Input 1

4 3 0
1 3 5

Output 1

1978

Input 2

3 5 1
2
0 1 2 5 6

Output 2

1494

Input 3

2333 2 5
2 3 4 5 6
114514 1919810

Output 3

264224065

Constraints

For $100\%$ of the data, $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$.

The constraints for each test case are as follows: