Problem Background

Java brought a tree to the problem-setting group today, and it was unreasonably taken over by MX.

Problem Description

MX now has a tree with $n$ nodes, each node having a number $a_i$.

Define the weight $w(x,y)$ of a path $(x,y)$ as the number obtained by sequentially writing down the numbers on all nodes along the shortest path from $x$ to $y$. For example, if the path sequentially passes through nodes with numbers $3, 21, 0, 5$, 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, so take 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, where 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

A single line containing an integer, representing the answer modulo $998244353$.

Sample Input and Output

Input Sample #1

3
1 2 3
1 2

Output Sample #1

538

Input Sample #2

3
5 21 0
1 2

Output Sample #2

6418

Input Sample #3

4
1 2 3 4
1 2 2

Output Sample #3

1900

Input Sample #4

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

Output Sample #4

7680868

Notes

Sample Explanation

Sample 1 Explanation: $1 + 12 + 123 + 2 + 21 + 23 + 3 + 32 + 321 = 538$.

Sample 2 Explanation: $5 + 521 + 5210 + 21 + 215 + 210 + 0 + 021 + 0215 = 6418$.

Data Range

This problem is bundled test cases.

Let $V = \max\{a_i\} + 1$.

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

见题面 Input 部分

见题面 Output 部分