P6132 [CTT Mutual Test 2019] Simple Counting

### Warning: abusing this problem will get your account banned. $\mathsf C \color{red}\mathsf{auchySheep}$ recently optimized the constants of his Number Theoretic Transform (NTT) template. Now he can easily handle $n=10^9$ within $0.1\text s$, so he plans to use the following simple counting problem to test your constant-factor optimization skills as well.

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.

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 one integer in $[0,998244352]$, the number of graphs satisfying the conditions modulo $998244353$.

[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