Little $C$ has a rooted tree with $n$ nodes, where the root is node $1$, and each node has at most two children.

The value of a node $x$ is defined as follows:

1. If $x$ has no children, its value is given in the input. It is guaranteed that the values of all such nodes are distinct.

2. If $x$ has children, its value is the maximum of its children's values with probability $p_x$, and the minimum of its children's values with probability $1-p_x$.

Now, Little $C$ wants to know the following: assuming the value of node $1$ has $m$ possible outcomes, where the $i$-th smallest possible value is $V_i$ with probability $D_i$ ($D_i > 0$), calculate:

$$\sum_{i=1}^{m}i\cdot V_i\cdot D_i^2$$

You need to output the answer modulo $998244353$.

Input

The first line contains a positive integer $n$.

The second line contains $n$ integers, where the $i$-th integer represents the parent of node $i$. The parent of node $1$ is $0$.

The third line contains $n$ integers. If node $i$ has no children, the $i$-th number is its value. Otherwise, the $i$-th number is $p_i \cdot 10000$. It is guaranteed that $p_i \cdot 10000$ is a positive integer.

Output

Output the answer.

Examples

Input 1

3
0 1 1
5000 1 2

Output 1

748683266

Note 1

The value of node $1$ is $1$ with probability $\frac{1}{2}$ and $2$ with probability $\frac{1}{2}$, so the answer is $\frac{5}{4}$.

Subtasks

For $10\%$ of the data, $1 \leq n \leq 20$.

For $20\%$ of the data, $1 \leq n \leq 400$.

For $40\%$ of the data, $1 \leq n \leq 5000$.

For $60\%$ of the data, $1 \leq n \leq 10^5$.

An additional $10\%$ of the data guarantees that the tree structure is random.

For $100\%$ of the data, $1 \leq n \leq 3 \times 10^5$ and $1 \leq w_i \leq 10^9$.

For all data, it is satisfied that $0 < p_i \cdot 10000 < 10000$, so it is easy to prove that the value of every leaf has a non-zero probability of being taken by the root.