Description

Jiutiao Keliang is a playful girl.

One day, she and her good friend Brother Fahai went to play an escape room. In front of them are $n$ switches, and at the beginning every switch is in the off state. To pass this level, the switches must reach a specified state. The target state is given by a binary array $s$ of length $n$. $s_i = 0$ means the $i$-th switch needs to be off in the end, and $s_i = 1$ means the $i$-th switch needs to be on in the end.

However, as challengers, Keliang and Fahai do not know $s$. So they decided to use a safer method: pressing randomly. Based on the shape and position of the switches, they used some “mystic” methods to assign each switch a weight $p_i$ ($p_i > 0$). Each time, they choose and press one switch with probability proportional to $p_i$ (the probability that the $i$-th switch is chosen is $\frac{p_i}{\sum^n_{j=1}p_j}$). After a switch is pressed, its state is flipped: on becomes off, and off becomes on. Note that each round of selection is completely independent.

During the process of pressing switches, once the current states of switches match $s$, the door in front of Keliang and Fahai will open. They will immediately stop pressing switches and move on to the next level. As a very lucky person, Keliang opened the door after pressing $\sum^n_{i=1} s_i$ times. To feel how good her luck was, she wants you to help her compute: using this random pressing method, what is the expected number of presses needed to pass this level?

Input Format

The first line contains an integer $n$, representing the number of switches.
The second line contains $n$ integers $s_i$ ($s_i\in \{0,1\}$), representing the target state of each switch.
The third line contains $n$ integers $p_i$, representing the weight of each switch.

Output Format

Output one line with one integer, representing the answer modulo $998244353$. That is, if the answer in simplest fractional form is $\frac{x}{y}$ ($x \ge 0$, $y \ge 1$, $\gcd(x, y) = 1$), you should output $x \times y^{-1} \bmod 998244353$.

2
1 1
1 1

4

8
1 1 0 0 1 1 0 0
1 2 3 4 5 6 7 8

858924815

Hint

[Sample Explanation #1]

In the first two presses, there is a probability of $\frac12$ to reach $s$, and a probability of $\frac12$ to return to the initial state. Therefore, the expected number of switch presses is:

$$\sum^{+\infty}_{i=1}2i\times \left(\frac12\right)^i=4$$

---

[Constraints and Notes]

Test Point	$n$	Other Notes	Test Point	$n$	Other Notes
$1$	$=2$	None	$6$	$\le 100$	$p_i\le 2,s_i=1$
$2$			$7$
$3$	$\le 8$		$8$		$\sum p_i\le 2\times 10^3$
$4$			$9$
$5$	$\le 100$	$p_i=1$	$10$		None

For $100\%$ of the testdata, it is guaranteed that $n\ge1$, $\sum^n_{i=1}p_i\le5\times10^4$, and $p_i\ge1$.

Translated by ChatGPT 5