P6132 [集训队互测 2019] 简单计数

## 警告，滥用本题者将被封号。 $\mathsf C \color{red}\mathsf{auchySheep}$ 近期优化了他的 快速数论变换 (NTT) 模板的常数，现在他能在 $0.1\text s$ 内轻松跑过 $n=10^9$ 了，所以他准备用下面的这个简单计数题也考验一下你的常数优化水平。

传说，在很久很久以前，有一张 $n​$ 个点的带标号**有向无环**图。每条边有一个颜色，为 $k$ 种不同颜色中的一种。这张图满足如下性质： - 每个点有不超过 $1$ 条出边 - 每个点的入边条数在集合 $S$ 中 由于某种原因，你想知道这样的图的个数。由于这样的图可能很多，你只要输出答案对 $998244353​$ 取模的值。 两个图不同当且仅当存在一条从某个点 $a$ 到某个点 $b$ 的有向边，它只在恰好一个图中出现，或在两个图中都出现但颜色不同。

第一行输入三个正整数 $n, k, |S|$。 第二行从小到大输入 $|S|$ 个不同的非负整数，表示 $S$ 集合中的元素。

输出一行一个 $[0,998244352]$ 的整数，表示符合题意的图的个数对 $998244353​$ 取模的值。

【样例一解释】 有如下 $13$ 个符合题意的图，其中 $a \to b$ 表示一条从 $a$ 连向 $b$ 的有向边： 1. 没有边 2. $1 \to 2$ 3. $2 \to 1$ 4. $1 \to3$ 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$ 【数据范围】 数据共分为 $7$ 个子任务。 - 子任务 $1$（$5$ 分）：$n \leq 8$。 - 子任务 $2$（$10$ 分）：$n \leq 5000$。 - 子任务 $3$（$30$ 分）：$n \leq 10^5$。 - 子任务 $4$（$20$ 分）：$n \leq 10^7$。 - 子任务 $5$（$15$ 分）：$n \leq 10^8$。 - 子任务 $6$（$10$ 分）：$S=\{0,1\}$。 - 子任务 $7$（$10$ 分）：无特殊限制。 对于 $100\%$ 的数据，$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 来源：2019 年集训队互测 Day5