P9437 "XYGOI round1" A Tree

Java brought a tree to the problem-setting group today, but the unreasonable MX took it for himself.

MX has a tree with $n$ nodes, and each node has a number $a_i$ on it. Define the weight $w(x,y)$ of a path $(x,y)$ as the number obtained by writing down, in order, all the numbers on the nodes along the shortest path from $x$ to $y$. For example, if the path passes through four nodes labeled with numbers $3,21,0,5$ in this order, then the weight of this path is $32105$. MX wants to know the sum of the weights of all paths in this tree, i.e., $\sum\limits_{x=1}^n\sum\limits_{y=1}^nw(x,y)$. The answer may be very large. Output it modulo $998244353$.

The first line contains a positive integer $n$. The second line contains $n$ non-negative integers $a_i$. The third line contains $n-1$ positive integers. The $i$-th number $p_i$ indicates that there is an edge between node $p_i$ and node $i+1$. It is guaranteed that $1\le p_i\le i$.

Output one integer in a single line, representing the answer modulo $998244353$.

### Sample Explanation Explanation for sample 1: $1+12+123+2+21+23+3+32+321=538$. Explanation for sample 2: $5+521+5210+21+215+210+0+021+0215=6418$. ### Constraints **This problem uses bundled testdata.** Let $V=\max\{a_i\}+1$. |Subtask|Points|$n\le$|$V\le $|Special Properties| |:-:|:-:|:-:|:-:|:-:| |0|5|$1000$|$10$|| |1|15|$8000$|$10^9$|| |2|15|$10^6$|$10^9$|$p_i=i$| |3|15|$10^6$|$10^9$|$p_i=1$| |4|50|$10^6$|$10^9$|| For $100\%$ of the testdata, $1\le n\le 10^6$ and $0\le a_i