Description

“咕噜咕噜....... 这是哪里”
你被传送到一个宝藏地，守卫者抛出了一个问题问你，给你一个字符串$S$(仅由小写字母组成)，向你询问这个字符串的最长 回文长度$m$是多少？您需要将这个最长长度回答给守卫者，但是由于紧张，你只有$\frac{1}{k}$的概率，说出正确答案。
若你成功说出正确答案了，现在你将进入了宝藏地，在你眼前的有$n$个藏品排成一排，每个藏品的价值为$a_i(1\leq i \leq n)$，琳琅满目的宝藏你又花了眼，你现在只想快点取走宝藏离开此地，但同时也要遵守守卫者的规定，即你现在只能取走一段长度不超过 $m$ 的连续区间的宝藏。
急急急，你能取走宝藏的最大价值的期望是多少？ 由于答案可能过大，需要您对$998244353$取模

Format

Input

第一行输入一个$len, n, k(1\leq len,n, k\leq 10^5)$，$len$表示字符串长度,$n$表示宝藏个数，$k$ 表示概率。
接下来首先输入一个字符串$S$表示守卫者的字符串;
其次，输入$n$个数字$a_i(-10^9 \leq a_i \leq 10^9)$, $a_i$表示每个宝藏的价值。

Output

输出取走宝藏最大价值的期望值对$998244353$取模的结果

可以证明，最终的答案一定可以表示成最简分数 $\frac{P}{Q}$,其中 $𝑃,𝑄$是正整数且$Q \not\equiv$ $0(mod 998244353)$。你需要输出一个整数 $0⩽𝑥<998244353$使得 $𝑥⋅𝑄≡𝑃(mod998244353)$,可以证明这样的 $x$ 是唯一的。

Samples

5 3 1
abcde
-9 10 2

10

2 3 3
cc
-10 -2 7

332748120

Hint

第一个样例：最长回文长度为1，宝藏最大价值为10, 进入宝藏地概率是$\frac{1}{1}$​，所以最大期望为 10