Background

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

Problem Description

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

Input Format

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 Format

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

3
1 2 3
1 2

538

3
5 21 0
1 2

6418

4
1 2 3 4
1 2 2

1900

6
10 23 16 3 125 1
1 1 1 1 1

7680868

Hint

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

For $100\%$ of the testdata, $1\le n\le 10^6$ and $0\le a_i<10^9$.

Translated by ChatGPT 5