P8486 「HGOI-1」Competition

$\text{HGOI}$ 举办了一场模拟赛。 为了增加选手们的积极性，$\text{HGOI}$ 的出题人根据题目难度划定了一个分数线。$\text{bh1234666}$ 会给超过这个分数线的选手发奖品。

众所周知，$\text{OI}$ 赛制的比赛有很大的运气成分。选手们往往不能发挥出真实水平。所以对于参赛的 $n$ 位选手，第 $i$ 位选手会有一个达到分数线的概率 $p_i$。 在模拟赛结束后就是最激动人心颁奖环节。 组委会的委员们设置了若干种类的奖品，并且每种奖品都有对应的价值。而他们对自己设置的奖品的发放有各自的要求： - $\text{uuku}$ 喜欢成双成对，所以对于他设置的**每种**奖品必须向**偶数个获奖选手**发放。 - $\text{rechinist}$ 喜欢跟 $\text{uuku}$ 对着干，所以对于他设置的**每种**奖品必须向**奇数个获奖选手**发放。 委员 $\text{uuku}$ 设置了 $A$ 种奖品，$a_i$ 表示他设置的第 $i$ 种奖品的价值。 委员 $\text{rechinist}$ 准备了 $B$ 种奖品，$b_i$ 表示他设置的第 $i$ 种奖品的价值。 当然**每个获奖选手**都将被发给**恰好**一份奖励。 选手们不关心每种奖品被发放了几次，但是他们关心有多少种奖品被发放了，因此选手们的积极性被定义为所有被发放的奖品的价值的乘积（每种奖品只会被乘一次）。 假如获奖人数使得委员会无法发放奖品， $\text{bh1234666}$ 会十分生气，拒绝提供资金购买奖品，使得选手积极性为 $0$ 。 现在，委员会已经知道了每个选手能达到分数线的概率 $p_i$，他们想知道选手们积极性的期望值为多少。 由于答案可能很大，所以你只需要给出对 $998244353$ 取模以后的结果。

第一行四个整数 $n$，$A$，$B$ 表示参赛人数和两位委员提出的金额序列的长度。 第二行 $n$ 个整数，表示 $n$ 选手达到分数线的概率 $p_i$（为了方便我们给出模 $998244353$ 意义下的概率）。 第三行 $A$ 个整数，表示 $\text{uuku}$ 提出的金额序列 $a$。 第四行 $B$ 个整数，表示 $\text{rechinist}$ 提出的金额序列 $b$。

一行一个整数，表示**选手们积极性的期望值**。

#### 样例1解释 $0\sim n$ 人达到分数线的概率依次为$\dfrac{1}{16}$，$\dfrac{1}{4}$，$\dfrac{3}{8}$，$\dfrac{1}{4}$，$\dfrac{1}{16}$。 对于 $0$ 人达到分数线无发放方案。 对于 $1$ 人达到分数线无发放方案。 对于 $2$ 人达到分数线有如下 $2$ 种发放方案。 $4$，$5$ 价值为 $20$ 对期望贡献为 $20\times \dfrac{3}{8}\times \dfrac{1}{2}=\dfrac{15}{4}$。 $5$，$4$ 价值为 $20$ 对期望贡献为 $20\times \dfrac{3}{8}\times \dfrac{1}{2}=\dfrac{15}{4}$。 对于 $3$ 人达到分数线无发放方案。 对于 $4$ 人达到分数线有如下 $32$ 种发放方案。 对于发放 $4$，$5$ 两种奖品一共有 $8$ 种方式。 每种价值均为 $20$ 对期望总贡献为 $20\times 8\times \dfrac{1}{16}\times \dfrac{1}{32}=\dfrac{5}{16}$。 对于发放 $1$，$4$，$5$ 三种奖品一共有 $12$ 种方式。 每种价值均为 $20$ 对期望总贡献为 $20\times 12\times \dfrac{1}{16}\times \dfrac{1}{32}=\dfrac{15}{32}$。 对于发放 $2$，$4$，$5$ 三种奖品一共有 $12$ 种方式。 价值均为 $40$ 对期望贡献为 $40\times 12\times \dfrac{1}{16}\times \dfrac{1}{32}=\dfrac{15}{16}$。 则总期望 $E=\dfrac{15}{4}+\dfrac{15}{4}+\dfrac{5}{16}+\dfrac{15}{32}+\dfrac{15}{16}=\dfrac{295}{32}\equiv 779878410 (\bmod\ 998244353)$。 #### 数据范围 本题采用**捆绑测试**，共有 $6$ 个 $\text{subtask}$，最终分数为所有 $\text{subtask}$ 分数之和。 $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \textbf{Score} & \textbf{特殊限制} \cr\hline 1 & 5 & n \le 5 \text{且} A \text{，}B \le 5 \cr\hline 2 & 10 & n \le 500 \text{且} A+B \le 500 \cr\hline 3 & 15 & n \le 2000 \text{且} 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} $$ 对于 $100\%$ 的数据，$1 \le A$，$B \le 2 \times 10^5$，$1 \le n \le 4 \times 10^5$，$1 \le a_i$，$b_i$，$p_i \le 998244352$。