Problem Description

Xiao Guo gives you $(n + 1)$ non-negative integers $a_0 \sim a_n$. For any $0 \leq i \leq n$, we have $a_i \in \{0, 1, 2\}$. Here, $a_i$ represents the number of dominant genes in the $i$-th person's genotype that control having a double eyelid, and in the following it also represents this organism.

Now, for any subsequence $b_{c_1} \sim b_{c_m}$ of the original sequence (where $1 \leq c_i < c_{i + 1} \leq m$, and $1 \leq i < m \leq n$), we mate $a_0$ with $b_{c_1}$ to obtain the 1st generation offspring, then mate that offspring with $b_{c_2}$ to obtain the 2nd generation offspring, and so on. Finally, we mate the $(m - 1)$-th generation offspring with $b_{c_m}$ to obtain the $m$-th generation offspring. We define the value of this subsequence as the probability that the $m$-th generation offspring has double eyelids.

Since he is very busy, he asks you to compute the average value of all subsequences, and output it modulo $998244353$.

Hint: Treat 0, 1, 2 as the three strings aa, Aa, AA. Mating two organisms means selecting a length $1$ subsequence from each string, and merging them with the uppercase letter first and the lowercase letter second. Each such resulting string is one possible genotype of the offspring.

Those starting with an uppercase letter are dominant traits, and those starting with a lowercase letter are recessive traits. Double eyelids are a dominant trait, and single eyelids are a recessive trait. Then map aa, Aa, AA back to the numbers 0, 1, 2.

Note: In this problem, we assume that whether someone has double or single eyelids is controlled by a pair of alleles A and a on an autosome, where A is completely dominant over a. The inheritance of this trait follows Mendel's law of segregation. We do not consider epigenetics, sex-linked inheritance, mutations, or interactions among gene expressions. No genotype has any lethal probability at the gamete or individual level, and all individuals can produce fertile gametes.

Input Format

The first line contains a positive integer $n$, separated by a space, where the meaning of $n$ is as described above.

The second line contains $(n + 1)$ non-negative integers. The $i$-th number in this line represents $a_i$.

Output Format

Output a single line containing one non-negative integer, which is the answer.

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

Hint

Constraints

For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^6, a_i \in \{0, 1, 2\}$.

For test point 1, $n = 1$.

For test point 2, $n = 2$.

For test points 3~5, $n \leq 5$.

For test points 6~10, $n \leq 7.5 \times 10^3$.

This problem has 20 test points. Each test point is worth 5 points, for a total of 100 points.

Translated by ChatGPT 5