题目背景

java 今天带了一棵树到出题组，然后被不讲理的 MX 占为己有了。

题目描述

于是 MX 有一棵 $n$ 个节点的树，每个点上有一个数字 $a_i$。

定义一条路径 $(x,y)$ 的权值 $w(x,y)$ 为，从 $x$ 走到 $y$ 的最短路径上，所有节点上的数字顺次写下后得到的数。如，顺次经过写有数字 $3,21,0,5$ 的四个节点，那么这个路径的权值为 $32105$。

MX 想知道这棵树所有路径的权值之和，即 $\sum\limits_{x=1}^n\sum\limits_{y=1}^nw(x,y)$ 为多少。

答案可能很大，对 $998244353$ 取模。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个非负整数 $a_i$。

第三行 $n-1$ 个正整数，第 $i$ 个数 $p_i$ 表示节点 $p_i$ 与节点 $i+1$ 之间有边。保证 $1\le p_i\le i$。

输出格式

一行一个整数，表示答案。答案对 $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

提示

样例解释

样例一解释：$1+12+123+2+21+23+3+32+321=538$。

样例二解释：$5+521+5210+21+215+210+0+021+0215=6418$。

数据范围

本题采用捆绑测试。

记 $V=\max\{a_i\}+1$。

Subtask	分值	$n\le$	$V\le$	特殊性质
0	5	$1000$	$10$
1	15	$8000$	$10^9$
2		$10^6$		$p_i=i$
3				$p_i=1$
4	50

对于 $100\%$ 的数据，$1\le n\le 10^6$，$0\le a_i<10^9$。