Background

$\text{HGOI}$ held a mock contest.

To boost the contestants' motivation, the problem setters of $\text{HGOI}$ set a cutoff score based on problem difficulty. $\text{bh1234666}$ will give prizes to contestants whose scores exceed this cutoff.

Problem Description

As everyone knows, contests under the $\text{OI}$ format involve a lot of luck. Contestants often cannot perform at their true level. Therefore, for the $n$ contestants, contestant $i$ has a probability $p_i$ of reaching the cutoff score.

After the mock contest comes the most exciting part: the award ceremony.

The committee members prepared several types of prizes, and each type has a corresponding value. Each member has their own requirements for how the prizes they set should be distributed:

• $\text{uuku}$ likes things in pairs, so for each type of prize he sets, it must be distributed to an even number of winners.

• $\text{rechinist}$ likes to oppose $\text{uuku}$, so for each type of prize he sets, it must be distributed to an odd number of winners.

Member $\text{uuku}$ set $A$ types of prizes, where $a_i$ is the value of the $i$-th type of prize he set.

Member $\text{rechinist}$ prepared $B$ types of prizes, where $b_i$ is the value of the $i$-th type of prize he set.

Of course, each winner will receive exactly one prize.

The contestants do not care how many times each type of prize is distributed, but they care about how many types of prizes are distributed. Therefore, the contestants' motivation is defined as the product of the values of all prize types that are distributed (each prize type is multiplied only once).

If the number of winners makes it impossible for the committee to distribute prizes, $\text{bh1234666}$ will be very angry and refuse to provide funds to buy prizes, making the contestants' motivation equal to $0$.

Now, the committee already knows each contestant's probability $p_i$ of reaching the cutoff score, and they want to know the expected value of the contestants' motivation.

Since the answer may be very large, you only need to output it modulo $998244353$.

Input Format

The first line contains four integers $n$, $A$, $B$, representing the number of contestants and the lengths of the two members' value sequences.

The second line contains $n$ integers, representing the probabilities $p_i$ that the $n$ contestants reach the cutoff score (for convenience, the probabilities are given modulo $998244353$).

The third line contains $A$ integers, representing the value sequence $a$ proposed by $\text{uuku}$.

The fourth line contains $B$ integers, representing the value sequence $b$ proposed by $\text{rechinist}$.

Output Format

Output one integer on a single line, representing the expected value of the contestants' motivation.

4 2 2
499122177 499122177 499122177 499122177
1 2 
4 5

779878410

Hint

Explanation for Sample 1

The probabilities that $0 \sim n$ people reach the cutoff score are respectively $\dfrac{1}{16}$, $\dfrac{1}{4}$, $\dfrac{3}{8}$, $\dfrac{1}{4}$, $\dfrac{1}{16}$.

For $0$ people reaching the cutoff score, there is no feasible distribution plan.

For $1$ person reaching the cutoff score, there is no feasible distribution plan.

For $2$ people reaching the cutoff score, there are the following $2$ distribution plans.

$4$, $5$, with value $20$, contributes $20\times \dfrac{3}{8}\times \dfrac{1}{2}=\dfrac{15}{4}$ to the expectation.

$5$, $4$, with value $20$, contributes $20\times \dfrac{3}{8}\times \dfrac{1}{2}=\dfrac{15}{4}$ to the expectation.

For $3$ people reaching the cutoff score, there is no feasible distribution plan.

For $4$ people reaching the cutoff score, there are the following $32$ distribution plans.

There are $8$ ways in total to distribute the two prize types $4$, $5$.

Each has value $20$, so the total contribution to the expectation is $20\times 8\times \dfrac{1}{16}\times \dfrac{1}{32}=\dfrac{5}{16}$.

There are $12$ ways in total to distribute the three prize types $1$, $4$, $5$.

Each has value $20$, so the total contribution to the expectation is $20\times 12\times \dfrac{1}{16}\times \dfrac{1}{32}=\dfrac{15}{32}$.

There are $12$ ways in total to distribute the three prize types $2$, $4$, $5$.

Each has value $40$, so the total contribution to the expectation is $40\times 12\times \dfrac{1}{16}\times \dfrac{1}{32}=\dfrac{15}{16}$.

Thus the total expectation is $E=\dfrac{15}{4}+\dfrac{15}{4}+\dfrac{5}{16}+\dfrac{15}{32}+\dfrac{15}{16}=\dfrac{295}{32}\equiv 779878410 (\bmod\ 998244353)$.

Constraints

This problem uses bundled testdata, with a total of $6$ $\text{subtask}$, and the final score is the sum of the scores of all $\text{subtask}$.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \textbf{Score} & \textbf{Special Constraints} \cr\hline 1 & 5 & n \le 5 \text{ and } A \text{, }B \le 5 \cr\hline 2 & 10 & n \le 500 \text{ and } A+B \le 500 \cr\hline 3 & 15 & n \le 2000 \text{ and } A+B\le 2000 \cr\hline 4 & 20 & n\text{, }A\text{, }B \le 5000 \cr\hline 5 & 20 & n \le 2\times 10^5 \text{, } A \text{, } B \le 10^5\cr\hline 6 & 30 & \cr\hline \end{array}$$

For $100\%$ of the data, $1 \le A \text{, } B \le 2 \times 10^5$, $1 \le n \le 4 \times 10^5$, and $1 \le a_i \text{, } b_i \text{, } p_i \le 998244352$.

Translated by ChatGPT 5