Description

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

Define the value of a node $x$ as follows:

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

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

Now Little C wants to know the following. Suppose the value of node $1$ has $m$ possible outcomes. Let the value of the $i$-th smallest outcome be $V_i$, and its probability be $D_i$ $(D_i>0)$. Compute:

You need to output the answer modulo $998244353$.

Input Format

The first line contains a positive integer $n$.

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

The third line contains $n$ integers. If node $i$ has no children, then 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 Format

Output the answer.

3
0 1 1
5000 1 2

748683266

Hint

Sample Explanation

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}$.

Constraints

• For $10\%$ of the testdata, $1\leq n\leq 20$.
• For $20\%$ of the testdata, $1\leq n\leq 400$.
• For $40\%$ of the testdata, $1\leq n\leq 5000$.
• For $60\%$ of the testdata, $1\leq n\leq 10^5$.
• Another $10\%$ of the testdata guarantees that the shape of the tree is random.
• For $100\%$ of the testdata, $1\leq n\leq 3\times 10^5$, $1\leq w_i\leq 10^9$.

For all testdata, $0 < p_i \cdot 10000 < 10000$, so it is easy to prove that every leaf value has a positive probability of being chosen by the root.

Translated by ChatGPT 5