CF1065E Side Transmutations

考虑一个字符集合$A$（$A$中元素互不相同）和一个长度为$n$的字符串$S$，其中$S$中的字符都属于集合$A$。 给你一个包含 $m$ 个整数的序列 $b$ ($b_1

第一行包括三个整数 $n$，$m$ 和 $|A|$（$2 \leq n \leq 10^9$，$1 \leq m \leq min(\frac{n}{2},2 * 10^5)$，$1\leq |A|\leq 10^9$），分别是字符串的长度，序列 $b$ 的大小，以及字符集 $A$ 的大小。 第二行包括 $m$ 个整数： $b_1,b_2,\dots,b_m$。

输出一个整数，即答案 $mod$ $998244353$ 的结果。

Here are all the distinct strings for the first example. The chosen letters 'a' and 'b' are there just to show that the characters in $ A $ are different. 1. "aaa" 2. "aab" = "baa" 3. "aba" 4. "abb" = "bba" 5. "bab" 6. "bbb"