题目背景

小 A 是 HCOI 国著名的演唱家，她打算开展一场巡回演出。

题目描述

HCOI 国由 $n$ 个城市构成，可以被抽象为一棵 $n$ 个节点的有根树，首都是树的根 $r$。小 A 打算从 $r$ 开始，遍历全国进行演出。

具体地，设 $x$ 是小 A 当前在的位置，记录一个序列 $s$：

• 初始时，$x=r$，$s=[r]$。
• 如果 $x$ 存在没有被访问过的儿子，任意选择一个儿子 $y$，在 $s$ 的最后插入 $y$，并前往 $y$。
• 如果不存在如上的 $y$：若 $x=r$，演出结束；否则前往 $x$ 的父亲。

我们称最后得到的 $s$ 是 $T$ 的一种遍历方法，选择不同的儿子可以得到多种遍历方法。可以发现遍历方法实际上是 $T$ 的 DFS 序。

小 A 的助手给出一张收费表 $\{w_{n-1}\}$，可以如下计算这次巡回演出的收入 $w(T,s)$：

• 对于 $i\in[1,n]$，小 A 经过 $T$ 上 $s_{i}\to s_{i\bmod n+1}$ 的简单路径上的点（不包含 $s_{i}$，包含 $s_{i\bmod n+1}$）。
• 每次到达一个节点时，若当前是第 $i$ 次到达，小 A 收获 $w_i$ 枚金币作为报酬。
• $w(T,s)$ 为小 A 收到的金币枚数的总和。

小 A 的助手还给出了本次演出的遍历方法 $\{s_n\}$，定义一棵树 $T$ 合法当且仅当 $\{s_n\}$ 是它的一种遍历方法。你需要求出所有不同的合法 $T$ 的 $w(T,s)$ 之和对 $998244353$ 取模后的结果。

两棵有根树 $T$ 和 $T'$ 不相同当且仅当它们的根节点不同或存在一条在 $T$ 中出现而 $T'$ 中未出现的边。

输入格式

本题包含多组数据。

第一行一个正整数 $T$ 代表数据组数。对于每组测试数据：

第一行一个正整数 $n$，表示 HCOI 国的城市数。

第二行 $n$ 个正整数 $s_1,s_2,\cdots,s_n$，表示小 A 本次演出的遍历方法。

第三行 $n-1$ 个非负整数 $w_1,w_2,\cdots,w_{n-1}$，表示演出的收费表。

输出格式

对于每组测试数据，输出一行一个整数表示所有合法的 $T$ 的 $w(T,s)$ 之和对 $998244353$ 取模后的结果。

7
2
1 2
1
3
1 2 3
1 2
4
1 2 3 4
1 2 3
5
1 3 5 2 4
1 3 2 1
6
6 2 3 4 1 5
3 2 4 7 4
7
1 3 2 4 5 6 7
12 32 84 27 83 11
8
1 7 3 2 8 4 6 5
11 45 14 19 19 8 10

2
10
42
182
1240
41336
124348

2
9
1 2 3 4 5 6 7 8 9
18 48 72 49 83 59 74 80
12
1 12 2 4 3 6 5 7 8 9 11 10
120 938 283 920 462 748 932 784 178 904 442

787978
522215784

1
4
1 2 3 4
1 0 0

20

提示

【样例解释 #1】

下文用 $(r,E)$ 来表示一棵有根树，其中 $E$ 是树的边集，$r$ 是树的根。

对于第一组数据，唯一一种合法的 $T$ 是 $(1,\{(1,2)\})$。小 A 经过两条路径 $1\to 2$ 和 $2\to 1$，经过了 $1,2$ 各一遍，故答案为 $1+1=2$。

对于第二组数据，合法的 $T$ 有 $(1,\{(1,2),(2,3)\}),(1,\{(1,2),(2,3)\})$，$w(T,s)$ 都是 $5$，故答案为 $5+5=10$。

对于第三组数据，合法的 $T$ 有 $(1,\{(1,2),(1,3),(1,4)\}),(1,\{(1,2),(1,3),(3,4)\}),(1,\{(1,2),$ $(2,3),(1,4)\}),(1,\{(1,2),(2,3),(2,4)\}),(1,\{(1,2),(2,3),(3,4)\})$，$w(T,s)$ 分别为 $9,8,8,$ $9,8$，故答案为 $9+8+8+9+8=42$。

对于第四组数据，一种合法的 $T$ 是 $(1,\{(1,3),(2,4),(3,2),(3,5)\})$，它的收入 $w(T,s)=13$。

【数据范围与约定】

本题采用捆绑测试。

子任务编号	$\boldsymbol{n\le}$	$\boldsymbol{\sum n\le}$	特殊性质	得分
$1$	$4$	$10^6$	A	$5$
$2$	$8$	$40$		$15$
$3$	$12$	$60$	无	$10$
$4$	$50$	$200$
$5$	$100$	$500$
$6$	$10^3$	$5\times 10^3$	B
$7$			无	$5$
$8$	$10^5$	$2\times 10^5$	B
$9$			无	$15$
$10$	$5\times10^5$	$10^6$

• 特殊性质 A：$i\in[1,n]$，$s_i=i$。
• 特殊性质 B：$w_1=1$，对于 $i\in[2,n-1]$，$w_i=0$。

对于所有数据，$1\le T\le 10^5$，$2\le n\le 5\times10^5$，$\sum n\le 10^6$，$0\le w_i<998244353$，$\{s_n\}$ 是一个 $1\sim n$ 的排列。