Description

The country of HCOI consists of $n$ cities, which is abstracted as a rooted tree with $n$ nodes, where the capital is the root $r$. Little A plans to start from $r$ and traverse all cities for a performance.

Specifically, let $x$ be Little A’s current position, and define a sequence $s$ as follows:

• Initially, $x = r$ and $s = [r]$.
• If $x$ has unvisited children, arbitrarily choose one child $y$, append $y$ to the end of $s$, and move to $y$.
• If no such $y$ exists: If $x = r$, the performance ends. Otherwise, move to $x$'s parent.

The final sequence $s$ is called a traversal method of $T$. Different choices of children yield multiple traversal methods. Note that traversal methods are essentially DFS orders of $T$.

Little A's assistant provides a fee table $\{w_{n-1}\}$. The revenue $w(T, s)$ of the tour is defined as:

• For $i \in [2, n]$, Little A traverses the simple path $s_{i-1} \to s_i$ on $T$ (excluding $s_{i-1}$, including $s_i$).
• Each time a node is visited, if it is the $i$-th time of arrival, Little A receives $w_i$ gold coins as payment.
• $w(T, s)$ is the total number of gold coins Little A collects.

The assistant also provides the traversal method $\{s_n\}$ for this performance. Little A tree $T$ is defined as valid if and only if $\{s_n\}$ is one of its traversal methods. You need to compute the sum of $w(T, s)$ over all distinct valid trees $T$, modulo $998244353$.

Two trees $T$ and $T'$ are considered distinct if they have different roots or there exists an edge present in one tree but not the other.

Input Format

Each single test case has multiple sets of test data.

The first line contains a positive integer $T$ representing the number of test cases. For each test case:

The first line contains a positive integer $n$, indicating the number of cities in HCOI.

The second line contains $n$ positive integers $s_1, s_2, \cdots, s_n$, representing the traversal method of A’s performance.

The third line contains $n-1$ non-negative integers $w_1, w_2, \cdots, w_{n-1}$, representing the fee table for the performance.

Output Format

For each test case, output a single line of integer representing the sum of all valid $T$'s $w(T)$ modulo $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

Hint

Constraints

This problem uses subtasks.

• Special Property A: For all $i \in [1, n]$, $s_i = i$.
• Special Property B: $w_1 = 1$, and for all $i \in [2, n-1]$, $w_i = 0$.

For all test cases, it is guaranteed that $1 \le T \le 10^5$, $2 \le n \le 5 \times 10^5$, $\sum n \le 10^6$, $0 \le w_i < 998244353$, $\{s_n\}$ is a permutation of $1,2,\cdots,n$.