Genetic Mating and Subsequence Averaging

You are given n+1 non‐negative integers a₀, a₁, ... , a_n, where each a_i is in the set {0, 1, 2}. They represent the number of dominant alleles controlling the double‐eyelid trait in each organism (0 stands for genotype aa, 1 for Aa, and 2 for AA). Note that the trait is dominant – an organism shows double eyelid if and only if its genotype is either Aa or AA.

Consider the following process: From the sequence a₁, ..., a_n (i.e. excluding a₀), you may choose any nonempty subsequence (preserving order). Suppose you choose indices c₁, c₂, …, c_m (with 1 ≤ c₁ < c₂ < ... < c_m ≤ n). Then the breeding process is defined as follows:

1. Mate organism a₀ with organism a_c1 to get the first generation offspring.
2. Then mate the offspring with organism a_c2 to get the second generation offspring.
3. Continue in this manner; finally, mate the (m-1)‑th generation offspring with a_cm to obtain the m‑th generation offspring.

The value of a chosen subsequence is defined as the probability that the final (m‑th generation) offspring exhibits the dominant (double‐eyelid) phenotype.

Genetics details:

• Interpret 0, 1, 2 as aa, Aa, AA respectively.
• In a mating, each parent contributes one allele at random (each allele is equally likely to be chosen). Note that an organism with genotype AA always passes an A; one with genotype aa always passes an a; and one with genotype Aa passes A with probability 1/2 and a with probability 1/2.
• An offspring will show the dominant trait if it receives at least one A (i.e. if its genotype is AA or Aa).

It is easy to verify that if an organism of genotype represented by x (where x is 0, 1, or 2) has a probability of passing the dominant allele equal to x/2, then if it mates with an organism with genotype y (with dominant allele probability y/2), the probability that their offspring shows the dominant phenotype is:

$$1 - \Bigl(1 - \frac{x}{2}\Bigr)\Bigl(1 - \frac{y}{2}\Bigr). $$

Furthermore, it can be shown by induction that if we start with a₀ (with dominant allele passing probability a0/2) and then mate sequentially with organisms whose values are a_c1, a_c2, ..., a_cm, the final probability of obtaining an offspring with the dominant trait is:

$$f(S) = 1 - \Bigl(1 - \frac{a_0}{2}\Bigr)\prod_{i\in S} \Bigl(1 - \frac{a_i}{2}\Bigr), $$

where S is the chosen subsequence (indices from 1 to n).

Your task is to compute the average value of f(S) over all nonempty subsequences of a₁, ... , a_n, and output the result modulo 998244353.

Note: A subsequence is obtained by choosing any nonempty subset of indices from 1 to n maintaining the original order. The number of such subsequences is 2n - 1.

inputFormat

The first line contains a single integer n (1 ≤ n).

The second line contains n+1 integers: a0 a1 ... an, where each ai is 0, 1, or 2.

outputFormat

Output a single integer representing the average value (i.e. the average probability that the final offspring shows the dominant phenotype) over all nonempty subsequences of a₁, ... , a_n, computed modulo 998244353.

The result is a rational number; you must output it modulo 998244353 using modular multiplicative inverses.

sample

1
0 0

0