题目描述
CauchySheep 近期优化了他的 快速数论变换(NTT) 模板的常数,现在他能在 0.1s 内轻松跑过 n=109 了,所以他准备用下面的这个简单计数题也考验一下你的常数优化水平。
传说,在很久很久以前,有一张 n 个点的带标号有向无环图。每条边有一个颜色,为 k 种不同颜色中的一种。这张图满足如下性质:
-
每个点有不超过 1 条出边
-
每个点的入边条数在集合 S 中
由于某种原因,你想知道这样的图的个数。由于这样的图可能很多,你只要输出答案对 998244353 取模的值。
两个图不同当且仅当存在一条从某个点 a 到某个点 b 的有向边,它只在恰好一个图中出现,或在两个图中都出现但颜色不同。
输入格式
第一行依次输入三个用空格分隔的正整数,n、k、∣S∣。
接下来第二行从小到大输入 ∣S∣ 个空格分隔的不同非负整数,表示 S 集合中的元素。
输出格式
输出一行一个 [0,998244352] 的整数,表示符合题意的图的个数对 998244353 取模的值。
样例 1
3 1 2
0 1
13
有如下13个符合题意的图,其中 a→b 表示一条从 a 连向 b 的有向边:
- 没有边
- 1→2
- 2→1
- 1→3
- 3→1
- 2→3
- 3→2
- 1→2→3
- 1→3→2
- 2→1→3
- 2→3→1
- 3→1→2
- 3→2→1
8 2 3
0 2 3
7497953
3000 2 3
0 1 3
500207304
876543210 233 4
0 1 2 3
467638557
数据范围与提示
对于所有数据,1≤n≤9×108,1≤k≤107,S 集合非空,S 集合中所有元素为 [0,3] 的非负整数。
数据共分为 7 个子任务。
- 子任务 1(5 分):n≤8。
- 子任务 2(10 分):n≤5000。
- 子任务 3(30 分):n≤105。
- 子任务 4(20 分):n≤107。
- 子任务 5(15 分):n≤108。
- 子任务 6(10 分):S={0,1}。
- 子任务 7(10 分):无特殊限制。