题目描述

给定 $n,m$ 和一个长度为 $n-1$ 的序列

$$w_1,w_2,\ldots,w_{n-1}.$$

对一个长度为 $n$、元素均在 $[1,m]$ 内的整数序列 $a$，小 M 用如下方式定义它的价值 $f(a)$：

• 初始系数 $X=1$；
• 有 $n-1$ 个机器人，编号分别为 $1$ 至 $n-1$，每个机器人分别做恰好一次检查；
• 第 $i$ 个机器人会检查是否对所有 $1\le j\le i$ 都满足

$$a_j=a_{n-i+j}.$$

若全部满足，则将 $X$ 改为 $X\cdot w_i$；否则 $X$ 不变；

• 最后记序列的价值为 $f(a)=X$。

小 M 想知道，在序列 $a$ 的每个位置 $a_i$ 都均匀独立随机生成的情况下，$f(a)$ 的期望是多少。你只需要求出其在模 $998244353$ 意义下的结果。

输入格式

输入第一行包含三个整数 $c,n,m$，分别表示测试点编号、序列长度和元素范围。$c=0$ 表示该测试点为样例。

输入第二行包含 $n-1$ 个非负整数 $w_1,w_2,\ldots,w_{n-1}$，表示每个机器人的系数。

输出格式

输出一行一个非负整数，表示序列价值的期望对 $998244353$ 取模后的结果。

样例 1 输入

0 3 2
3 2

样例 1 输出

249561091

样例 1 解释

• 当 $a=[1,1,1]$ 或 $a=[2,2,2]$ 时，$f(a)=3\times 2=6$；
• 当 $a=[1,2,1]$ 或 $a=[2,1,2]$ 时，$f(a)=3$；
• 当 $a=[1,1,2]$、$[2,2,1]$、$[1,2,2]$ 或 $[2,1,1]$ 时，$f(a)=1$。

因此

$$\mathbb E[f(a)] = \frac{6\times 2+3\times 2+1\times 4}{8}=\frac{11}{4}\equiv 249561091\pmod{998244353}.$$

样例 2 输入

0 5 5
1 1 1 1

样例 2 输出

1

样例 2 解释

机器人不会改变 $X$ 的值，因此对所有序列 $a$，$f(a)$ 均等于 $1$，故期望也为 $1$。

数据范围

对于每组测试数据，均有：

• $2\le n\le 800$；
• $1\le m\le 10^5$；
• $0\le w_i<998244353$。

测试点编号	$n\le$	特殊性质
1	5	$m\le 5$
2, 3	10	无
4, 5	20
6, 7	50
8 ~ 10	150
11, 12	220
13	300
14, 15	400	$w_i=0$
16		无
17, 18	500
19, 20	600
21, 22	700
23 ~ 25	800