题目描述

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

魔法纪元元年。

$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

输出

12

设三种颜色分别为 $\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

输出

10

样例 3

输入

2 100 20
50 50

输出

164333748

样例 4

输入

5 2333 666
300 1000 233 200 600

输出

119409616

样例 5

输入

5 30000 0
4000 5000 6000 7000 8000

输出

522962185

样例 6

输入

6 50000 12345
9896 104 15000 13000 8000 4000

输出

940147981

数据范围与提示