P4945 - 「雅礼集训 2018 Day4」Magic

Problem

P4945「雅礼集训 2018 Day4」Magic

Limits : Time Limit : - MS Memory Limit : - KB

Judgment Tips : 5s 512m

Description

前进！前进！不择手段地前进！——托马斯 · 维德

魔法纪元元年。

1453 年 5 月 3 日 16 时，高维碎片接触地球。

1453 年 5 月 28 日 21 时，碎片完全离开地球。

1453 年，君士坦丁堡被围城，迪奥娜拉接触到四维泡沫空间，成为魔法师，最终因高维碎片消失失去魔力而身死。

为了改写这段历史，你不惜耗费你珍藏已久的魔术卡来回到魔法纪元元年。

在使用这些魔术卡之前，你却对它们的排列起了兴趣...

桌面上摆放着 $m$ 种魔术卡，共 $n$ 张，第 $i$ 种魔术卡数量为 $a_i$，魔术卡顺次摆放，形成一个长度为 $n$ 的魔术序列，在魔术序列中，若两张相邻魔术卡的种类相同，则它们被称为一个魔术对。

两个魔术序列本质不同，当且仅当存在至少一个位置，使得两个魔术序列这个位置上的魔术卡的种类不同，求本质不同的恰好包含 $k$ 个魔术对的魔术序列的数量，答案对 $998244353$ 取模。

Input Format

第一行三个整数 $m, n, k$。

第二行 $m$ 个正整数，第 $i$ 个正整数表示 $a_i$。

Output Format

一行一个整数表示答案。

Sample Input 1

3 5 1
2 2 1

Sample Output 1

Sample Input 2

3 6 0
1 2 3

Sample Output 2

Sample Input 3

2 100 20
50 50

Sample Output 3

164333748

Sample Input 4

5 2333 666
300 1000 233 200 600

Sample Output 4

119409616

Sample Input 5

5 30000 0
4000 5000 6000 7000 8000

Sample Output 5

522962185

Sample Input 6

6 50000 12345
9896 104 15000 13000 8000 4000

Sample Output 6

940147981

Hint

样例解释 1

设三种颜色分别为 $\rm A, B, C$ ，则合法的 $12$ 种方案分别为： $\rm (AABCB)$ ， $\rm (ABBAC)$ ， $\rm (ABBCA)$ ， $\rm (ACABB)$ ， $\rm (ACBBA)$ ， $\rm (BAABC)$ ， $\rm (BAACB)$ ， $\rm (BBACA)$ ， $\rm (BCAAB)$ ， $\rm (BCBAA)$ ， $\rm (CABBA)$ ， $\rm (CBAAB)$

测试点编号	$m$	$n$	$k$	特殊性质
1	$=2$	$\leq 300$	$= 1$
2	$=2$	$\leq 300$	$= 2$
3	$=2$	$\leq 300$
4	$=2$	$\leq 300$
5	$=3$	$\leq 16$
6	$=3$	$\leq 16$
7	$=3$	$\leq 80$
8	$=3$	$\leq 80$
9	$=3$	$\leq 80$
10	$\leq 100$	$\leq 100$	$= 0$	$m = n$
11	$\leq 2000$	$\leq 5000$	$= 0$
12	$\leq 2000$	$\leq 5000$	$= 0$
13	$\leq 2000$	$\leq 5000$	$= 0$
14	$\leq 2000$	$\leq 5000$
15	$\leq 2000$	$\leq 5000$
16	$\leq 2000$	$\leq 5000$
17	$\leq 20000$	$\leq 100000$	$= 0$	$a_i$ 均相等且 $\leq 20$
18	$\leq 20000$	$\leq 100000$	$= 0$	$a_i$ 均相等且 $\leq 20$
19	$\leq 20000$	$\leq 100000$	$= 0$	$a_i$ 均相等且 $\leq 20$
20	$\leq 20000$	$\leq 100000$	$= 0$
21	$\leq 20000$	$\leq 100000$	$= 0$
22	$\leq 20000$	$\leq 100000$
23	$\leq 20000$	$\leq 100000$
24	$\leq 20000$	$\leq 100000$
25	$\leq 20000$	$\leq 100000$

对于 $100 \%$ 的数据满足 $1 \leq m \leq 20000, 0 \leq k \leq n \leq 100000, \sum_{i = 1}^{m} a_i = n$ 。

测试点编号	\(m\)	\(n\)	\(k\)	特殊性质
1	\(=2\)	\(\leq 300\)	\(= 1\)
2	\(=2\)	\(\leq 300\)	\(= 2\)
3	\(=2\)	\(\leq 300\)
4	\(=2\)	\(\leq 300\)
5	\(=3\)	\(\leq 16\)
6	\(=3\)	\(\leq 16\)
7	\(=3\)	\(\leq 80\)
8	\(=3\)	\(\leq 80\)
9	\(=3\)	\(\leq 80\)
10	\(\leq 100\)	\(\leq 100\)	\(= 0\)	\(m = n\)
11	\(\leq 2000\)	\(\leq 5000\)	\(= 0\)
12	\(\leq 2000\)	\(\leq 5000\)	\(= 0\)
13	\(\leq 2000\)	\(\leq 5000\)	\(= 0\)
14	\(\leq 2000\)	\(\leq 5000\)
15	\(\leq 2000\)	\(\leq 5000\)
16	\(\leq 2000\)	\(\leq 5000\)
17	\(\leq 20000\)	\(\leq 100000\)	\(= 0\)	\(a_i\) 均相等且 \(\leq 20\)
18	\(\leq 20000\)	\(\leq 100000\)	\(= 0\)	\(a_i\) 均相等且 \(\leq 20\)
19	\(\leq 20000\)	\(\leq 100000\)	\(= 0\)	\(a_i\) 均相等且 \(\leq 20\)
20	\(\leq 20000\)	\(\leq 100000\)	\(= 0\)
21	\(\leq 20000\)	\(\leq 100000\)	\(= 0\)
22	\(\leq 20000\)	\(\leq 100000\)
23	\(\leq 20000\)	\(\leq 100000\)
24	\(\leq 20000\)	\(\leq 100000\)
25	\(\leq 20000\)	\(\leq 100000\)