Description

Legend says that a long, long time ago, there was a labeled directed acyclic graph (DAG) with $n$ vertices. Each edge has a color, which is one of $k$ different colors. The graph satisfies the following properties:

• Each vertex has at most $1$ outgoing edge.
• The in-degree of each vertex belongs to the set $S$.

For some reason, you want to know how many such graphs there are. Since the number may be huge, 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 two graphs, or 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 increasing order, representing the elements of the set $S$.

Output Format

Output one integer in $[0,998244352]$, the number of graphs satisfying the conditions modulo $998244353$.

3 1 2
0 1

13

8 2 3
0 2 3

7497953

3000 2 3
0 1 3

500207304

10000000 3 2
0 3

238588124

876543210 233 4
0 1 2 3

467638557

Hint

[Explanation for Sample 1]
There are $13$ graphs satisfying the conditions. Here $a \to b$ denotes 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$.

[Constraints]
The testdata 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 constraints.

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

By: fjzzq2002
Source: CTT Mutual Test 2019 Day 5.

Input Format

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

Output Format

Output one integer in $[0,998244352]$, the number of graphs satisfying the conditions modulo $998244353$.

Hint

[Explanation for Sample 1]
There are $13$ graphs satisfying the conditions. Here $a \to b$ denotes 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$.

[Constraints]
The testdata 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 constraints.

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

By: fjzzq2002
Source: CTT Mutual Test 2019 Day 5.

Translated by ChatGPT 5