时空限制

1S/512M

题目描述

灯光师准备为一条由 $n$ 盏灯组成的灯带设置颜色。可用颜色编号为 $1,2,\ldots,m$，第 $i$ 盏灯的颜色记为 $a_i$。

这条灯带需要恰好使用 $k$ 种不同的颜色。除此之外，灯光师还给出了长度为 $n-2$ 的检查表 $b$：从第 $i$ 盏灯开始的连续三盏灯 $a_i,a_{i+1},a_{i+2}$，必须恰好包含 $b_i$ 种不同颜色，其中 $1\le i\le n-2$。

请计算满足全部要求的配色方案数，并将答案对 $998244353$ 取模。两种方案只要有一盏灯的颜色编号不同，就视为不同。若不存在符合要求的方案，答案为 $0$。

格式

输入格式

第一行包含三个整数 $n,m,k$，表示灯的数量，可用颜色数量和需要的颜色数。

第二行包含 $n-2$ 个整数 $b_1,b_2,\ldots,b_{n-2}$，具体含义见题目描述。

输出格式

输出一个整数，表示配色方案数对 $998244353$ 取模后的结果。

样例

样例输入 #1

4 3 2
2 2

样例输出 #1

30

样例输入 #2

3 3 3
3

样例输出 #2

6

样例解释 #2

三盏灯必须分别使用三种不同的颜色，共有 $6$ 种方案。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

特殊性质 A：对于所有 $1 \le i \le n-2$，均有 $b_i=3$。

对于 $100\%$ 的数据，满足 $3 \le n \le 2000$，$1 \le m < 998244353$，$1 \le k \le \min(n,m)$，$1 \le b_i \le 3$。