题目描述

小郭给你 $(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$。

输出格式

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

2
2 1 0

415935148

50
2 1 2 1 0 0 2 2 0 0 1 2 0 0 0 2 0 0 1 2 1 1 1 1 1 0 1 1 1 0 1 2 0 1 1 0 1 1 2 0 1 0 0 1 1 1 0 1 2 1 1

576313280

提示

样例 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