Problem Description

Legend has it that a long, long time ago, there was a labeled directed acyclic graph with $n$ vertices. Each edge had a color, which was one of $k$ different colors. This graph satisfied the following properties:

• Each vertex had at most one outgoing edge.
• The number of incoming edges for each vertex was in the set $S$.

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

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

Input Format

The first line contains three positive integers $n, k, |S|$.
The second line contains $|S|$ distinct non-negative integers in ascending order, representing the elements in set $S$.

Output Format

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

Sample Input and Output

Input Sample #1

3 1 2
0 1

Output Sample #1

13

Input Sample #2

8 2 3
0 2 3

Output Sample #2

7497953

Input Sample #3

3000 2 3
0 1 3

Output Sample #3

500207304

Input Sample #4

10000000 3 2
0 3

Output Sample #4

238588124

Input Sample #5

876543210 233 4
0 1 2 3

Output Sample #5

467638557

Notes

Sample 1 Explanation

There are $13$ valid graphs, where $a \to b$ represents a directed edge from $a$ to $b$:

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

Data Range

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.

For $100\%$ of the data, $1 \le n \le 9 \times 10^8$, $1 \le k \le 10^7$, $S \neq \varnothing$, $S \subseteq \{0, 1, 2, 3\}$.

By: fjzzq2002
Source: 2019 Training Team Mutual Test Day 5

见题面 Input 部分

见题面 Output 部分