Keliang Jiutiao 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 initially, all switches are in the off state. To pass this level, the switches must reach a specified state. The target state is given by a 01 array $s$ of length $n$, where $s_i = 0$ means the $i$-th switch needs to be off at the end, and $s_i = 1$ means the $i$-th switch needs to be on at the end.

However, as the challengers, Keliang and Fahai do not know $s$. Therefore, they decide to adopt a safer method: pressing them blindly. Based on the appearance and position of the switches, they use some metaphysical methods to assign a weight $p_i$ ($p_i > 0$) to each switch. Each time, they choose and press a switch with a probability proportional to $p_i$ (the probability that the $i$-th switch is chosen is $\frac{p_i}{\sum_{j=1}^n p_j}$).

After a switch is pressed, its state is toggled, i.e., on becomes off, and off becomes on. Note that each choice is completely independent.

During the process of pressing the switches, once the current state of the switches reaches $s$, the door in front of Keliang and Fahai will open, and they will immediately stop the process and proceed to the next level. As a lucky person, Keliang opened the door after pressing the switches $\sum_{i=1}^n s_i$ times. To feel how lucky she is, Keliang wants you to help her calculate the expected number of times the switches need to be pressed to pass this level using this random pressing method.

Input

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 the switches. The third line contains $n$ integers $p_i$, representing the weight of each switch.

Output

Output a single integer representing the answer modulo $998244353$. That is, if the simplest fraction representation of the answer is $\frac{x}{y}$ ($x \ge 0, y \ge 1, \gcd(x, y) = 1$), you need to output $x \times y^{-1} \pmod{998244353}$.

Examples

Input 1

2
1 1
1 1

Output 1

4

Note 1

After pressing the switches twice, there is a $\frac{1}{2}$ probability of reaching $s$ and a $\frac{1}{2}$ probability of returning to the original state. Therefore, the expected number of switch presses is: $$\sum_{i=1}^{+\infty} 2i \times \left(\frac{1}{2}\right)^i = 4$$

Input 2

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

Output 2

858924815

Constraints

For 100% of the data, it is guaranteed that $n \ge 1$, $\sum_{i=1}^n p_i \le 5 \times 10^4$, and $p_i \ge 1$.