H. LCA Determinant
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
"As elegant as." (Guess a mathematician connected to a famous determinant.)
—Beggar's Chicken

You are given a tree consisting of $$$n$$$ vertices. Vertices are numbered from $$$1$$$ to $$$n$$$, while vertex $$$1$$$ is the root of the tree. Each vertex has a weight $$$a_i$$$.

Consider a matrix $$$$$$ A := \begin{pmatrix} a_{\operatorname{lca}(i,j)} \end{pmatrix}_{n \times n} = \begin{pmatrix} a_{\operatorname{lca}(1,1)} & a_{\operatorname{lca}(1,2)} & \dots & a_{\operatorname{lca}(1,n)} \\ a_{\operatorname{lca}(2,1)} & a_{\operatorname{lca}(2,2)} & \dots & a_{\operatorname{lca}(2,n)} \\ \vdots & \vdots & \ddots & \vdots \\ a_{\operatorname{lca}(n,1)} & a_{\operatorname{lca}(n,2)} & \dots & a_{\operatorname{lca}(n,n)} \end{pmatrix} $$$$$$ where $$$\operatorname{lca}(i,j)$$$ denotes the lowest common ancestor of vertex $$$i$$$ and vertex $$$j$$$.

Please calculate the determinant of matrix $$$A$$$. Since the answer could be large, output your answer modulo $$$998244353$$$.

Input

There is only one test case in each test file.

The first line consists of only one integer $$$n$$$ ($$$2 \leq n \leq 5 \times 10^5$$$), the size of the tree.

The second line consists of $$$n-1$$$ integers $$$p_2, p_3, \dots, p_n$$$ ($$$1 \leq p_i \lt i$$$), where $$$p_i$$$ denotes the parent of vertex $$$i$$$.

The last line consists of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \lt 998244353$$$), the weight of each vertex.

It is guaranteed that the edges form a valid rooted tree.

Output

Output a single integer, representing $$$\det A \bmod 998244353$$$.

Examples
Input
3
1 2
5 1 4
Output
998244293
Input
5
1 1 2 2
1 2 3 4 5
Output
12
Input
5
1 1 3 4
20231126 514514514 19260817 353442899 112358111
Output
86351415
Note

In the first example, $$$$$$ \det{A} = \det{\begin{pmatrix} 5 & 5 & 5 \\ 5 & 1 & 1 \\ 5 & 1 & 4 \end{pmatrix}} = -60 $$$$$$

In the second example, $$$$$$ \det{A} = \det{\begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 1 & 2 & 2 \\ 1 & 1 & 3 & 1 & 1 \\ 1 & 2 & 1 & 4 & 2 \\ 1 & 2 & 1 & 2 & 5 \end{pmatrix}} = 12 $$$$$$