#[3081].「2019 集训队互测 Day 5」简单计数

内存限制：512 MB 时间限制：7000 ms

CauchySheep 近期优化了他的快速数论变换(NTT) 模板的常数，现在他能在 $\text{0.1s}$ 内轻松跑过 $n=10^9$ 了，所以他准备用下面的这个简单计数题也考验一下你的常数优化水平。传说，在很久很久以前，有一张 $n$ 个点的带标号有向无环图。每条边有一个颜色，为 $k$ 种不同颜色中的一种。这张图满足如下性质： - 每个点有不超过 $1$ 条出边 - 每个点的入边条数在集合 $S$ 中由于某种原因，你想知道这样的图的个数。由于这样的图可能很多，你只要输出答案对 $998244353$ 取模的值。两个图不同当且仅当存在一条从某个点 $a$ 到某个点 $b$ 的有向边，它只在恰好一个图中出现，或在两个图中都出现但颜色不同。

第一行依次输入三个用空格分隔的正整数，$n$、$k$、$|S|$。

接下来第二行从小到大输入 $|S|$ 个空格分隔的不同非负整数，表示 $S$ 集合中的元素。

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

有如下13个符合题意的图，其中 $a \rightarrow b$ 表示一条从 $a$ 连向 $b$ 的有向边：

没有边
$1 \rightarrow 2$
$2 \rightarrow 1$
$1 \rightarrow 3$
$3 \rightarrow 1$
$2 \rightarrow 3$
$3 \rightarrow 2$
$1 \rightarrow 2 \rightarrow 3$
$1 \rightarrow 3 \rightarrow 2$
$2 \rightarrow 1 \rightarrow 3$
$2 \rightarrow 3 \rightarrow 1$
$3 \rightarrow 1 \rightarrow 2$
$3 \rightarrow 2 \rightarrow 1$

对于所有数据，$1 \leq n \leq 9 \times 10^8$，$1 \leq k \leq 10^7$，$S$ 集合非空，$S$ 集合中所有元素为 $[0,3]$ 的非负整数。

数据共分为 $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$ 分）：无特殊限制。

样例输入 1

3 1 2
0 1

样例输出 1

样例输入 2

8 2 3
0 2 3

样例输出 2

样例输入 3

3000 2 3
0 1 3

样例输出 3

500207304

样例输入 4

876543210 233 4
0 1 2 3

样例输出 4

467638557

3081 「2019 集训队互测 Day 5」简单计数

题目描述

输入格式

输出格式

样例 1

样例 2

样例 3

样例 4

数据范围与提示

样例