問題文

長さ $N$ の数列 $(A_1, A_2, \dots, A_N)$ と 長さ $N-1$ の数列 $(B_2, B_3, \dots, B_N), (C_2, C_3, \dots, C_N), (P_2, P_3, \dots, P_N)$ が与えられます。

$\displaystyle M = \sum_{1 \le i \le N} A_i$ とします。

$M$ 頂点 の木 $G(V, E)$ を以下のように定義します。

• $1 \le i \le N$, $1\le j \le A_i$ について、 $(i, j) \in V$ である。この頂点を頂点 $(i, j)$ と呼ぶ。
• $1 \le i \le N$, $1\le j \lt A_i$ について、 頂点 $(i, j)$ と頂点 $(i, j+1)$ を結ぶ辺が存在する。
• $2 \le i \le N$ について、 頂点 $(i, B_i)$ と頂点 $(P_i, C_i)$ を結ぶ辺が存在する。
• これら以外に頂点を結ぶ辺は存在しない。

ここで、制約から $G(V, E)$ が木であることは保証されます。

以下の値を求めて $998244353$ で割った余りを出力してください。

$\displaystyle\sum_{u \in V}\sum_{v \in V} \text{dist}(u, v)$

ただし、$\text{dist}(u, v)$ は頂点 $u$ と頂点 $v$ を両端点とする単純パスに含まれる辺の数です。

制約

• 入力はすべて整数
• $2 \le N \le 10^5$
• $1 \le A_i \le 10^9 \space (1 \le i \le N)$
• $1 \le B_i \le A_i \space (2 \le i \le N)$
• $1 \le C_i \le A_{P_i} \space (2 \le i \le N)$
• $1 \le P_i \lt i \space (2 \le i \le N)$

入力

$N$
$A_1$ $A_2$ $\cdots$ $A_N$
$B_2$ $B_3$ $\cdots$ $B_N$
$C_2$ $C_3$ $\cdots$ $C_N$
$P_2$ $P_3$ $\cdots$ $P_N$

出力

答えを出力してください。

サンプル

サンプル1

入力

2
2 3
2
1
1

出力

36

入力で与えられる木 $G(V, E)$ は以下の図のようになります。

3
2 3 3
1 2
2 2
1 2

140