#6503. 「雅礼集训 2018 Day4」Magic

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

魔法纪元元年。

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

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

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

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

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

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

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

输入格式

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

第二行 m 个正整数,第 i 个正整数表示 a_i

输出格式

一行一个整数表示答案。

样例

样例输入 1

3 5 1
2 2 1

样例输出 1

12

样例解释 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)

样例输入 2

3 6 0
1 2 3

样例输出 2

10

样例输入 3

2 100 20
50 50

样例输出 3

164333748

样例输入 4

5 2333 666
300 1000 233 200 600

样例输出 4

119409616

样例输入 5

5 30000 0
4000 5000 6000 7000 8000

样例输出 5

522962185

样例输入 6

6 50000 12345
9896 104 15000 13000 8000 4000

样例输出 6

940147981

数据范围与提示

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

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