CauchySheep has recently optimized the constant factor of his Number Theoretic Transform (NTT) template, and now he can easily run $n=10^9$ in under $\text{0.1s}$. Therefore, he has prepared the following simple counting problem to test your constant optimization skills.

Legend has it that a long, long time ago, there was a labeled Directed Acyclic Graph (DAG) with $n$ vertices. Each edge has a color, chosen from $k$ different colors. The graph satisfies the following properties:

• Each vertex has at most $1$ outgoing edge.
• The number of incoming edges for each vertex belongs to the set $S$.

For some reason, you want to know the number of such graphs. Since there may be many such graphs, you only need to output the answer modulo $998244353$.

Two graphs are different if and only if there exists a directed edge from some vertex $a$ to some vertex $b$ that appears in exactly one of the graphs, or appears in both but with different colors.

Input

The first line contains three space-separated positive integers: $n$, $k$, and $|S|$.

The second line contains $|S|$ distinct non-negative integers in increasing order, representing the elements of the set $S$.

Output

Output a single integer in the range $[0, 998244352]$, representing the number of such graphs modulo $998244353$.

Examples

Input 1

3 1 2
0 1

Output 1

13

Note 1

There are 13 such graphs, where $a \rightarrow b$ denotes a directed edge from $a$ to $b$:

1. No edges
2. $1 \rightarrow 2$
3. $2 \rightarrow 1$
4. $1 \rightarrow 3$
5. $3 \rightarrow 1$
6. $2 \rightarrow 3$
7. $3 \rightarrow 2$
8. $1 \rightarrow 2 \rightarrow 3$
9. $1 \rightarrow 3 \rightarrow 2$
10. $2 \rightarrow 1 \rightarrow 3$
11. $2 \rightarrow 3 \rightarrow 1$
12. $3 \rightarrow 1 \rightarrow 2$
13. $3 \rightarrow 2 \rightarrow 1$

Input 2

8 2 3
0 2 3

Output 2

7497953

Input 3

3000 2 3
0 1 3

Output 3

500207304

Input 4

876543210 233 4
0 1 2 3

Output 4

467638557

Subtasks

For all test cases, $1 \leq n \leq 9 \times 10^8$, $1 \leq k \leq 10^7$, the set $S$ is non-empty, and all elements in $S$ are non-negative integers in the range $[0, 3]$.

The data is divided into $7$ subtasks.

• Subtask 1 ($5$ points): $n \leq 8$.
• Subtask 2 ($10$ points): $n \leq 5000$.
• Subtask 3 ($30$ points): $n \leq 10^5$.
• Subtask 4 ($20$ points): $n \leq 10^7$.
• Subtask 5 ($15$ points): $n \leq 10^8$.
• Subtask 6 ($10$ points): $S=\{0,1\}$.
• Subtask 7 ($10$ points): No special restrictions.