P6636 「JYLOI Round 1」性状

小郭给你 $(n + 1)$ 个非负整数 $a_0 \sim a_n$，对于任意 $0 \leq i \leq n$ 有 $a_i \in \{0, 1, 2\}$，其中 $a_i$ 表示第 $i$ 个人的基因中控制双眼皮的显性基因个数，在下文中也代表着这个生物。 现在对于原序列中的任意一个子序列 $b_{c_1} \sim b_{c_m}$（其中 $1 \leq c_i < c_{i + 1} \leq m$，并且 $1 \leq i < m \leq n$），将 $a_0$ 和 $b_{c_1}$ 进行交配，得到子一代，并将子一代和 $b_{c_2}$ 交配，得到子二代，以此类推，最后将子 $(m - 1)$ 代与 $b_{c_m}$ 进行交配，得到子 $m$ 代，我们定义这个子序列的价值为子 $m$ 代为双眼皮的概率。 由于他很忙，于是他现在请你帮他求出所有子序列的价值的平均值在模 $998244353$ 意义下的值。 **提示**：把 0、1、2 分别看作 ``aa``、``Aa``、``AA`` 三种字符串，两个生物进行交配，就是选择每个字符串间长度为 1 的子序列进行大写字母在前，小写在后的合并，其中这样的一个字符串为子代一种可能的基因组成。 其中大写字母开头的为显性性状，小写字母开头为隐性性状。双眼皮为显性性状，单眼皮为隐性性状，结果 ``aa``、``Aa``、``AA`` 分别再对应回数字 0、1、2。 **注意**，在本题中，我们认为眼皮的单双由位于常染色体上的一对等位基因 ``A`` 和 ``a`` 控制，其中 ``A`` 相对 ``a`` 为完全显性。且该性状的遗传遵循孟德尔的分离定律，并不考虑表观遗传、从性遗传、突变、基因表达的相互影响，所有基因型的配子和个体均无致死概率，所有个体均能产生可育配子。

输入的第 1 行有一个正整数 $n$，中间用一个空格隔开，$n$ 的含义如题所述。 第二行有 $(n + 1)$ 个非负整数，这一行中的第 $i$ 个数表示 $a_i$。

输出只有一行一个非负整数，表示答案。

## 样例 1 解释 子序列 $\{1\}$、$\{0\}$、$\{1, 0\}$ 的价值分别为 $1$、$1$ 和 $\dfrac{3}{4}$，平均价值为 $\dfrac{11}{12}$，对 $998244353$ 取模后的结果为 $415935148$。 ## 数据范围 对于 $100\%$ 的测试数据，$1 \leq n \leq 5 \times 10^6, a_i \in \{0, 1, 2\}$。 对于测试点 1，$n = 1$。 对于测试点 2，$n = 2$。 对于测试点 3~5，$n \leq 5$。 对于测试点 6~10，$n \leq 7.5 \times 10^3$。 本题共有 20 个测试点，每个测试点 5 分，共 100 分。 ## 题目来源 「JYLOI Round 1」 B Idea：abcdeffa & LiuXiangle Solution：LiuXiangle Data：LiuXiangle