Sum of Revenues over Legal DFS Trees

In HCOI country there are n cities, which can be represented as a rooted tree with n nodes. The capital, which is the root r, is given by the first element of a DFS‐preorder traversal s of the tree. A DFS traversal is defined as follows:

• Initially, let x = r and s = [r].
• If the current node x has at least one unvisited child, pick any one of them (say y), append y to the sequence s, and set x = y.
• If no unvisited child exists and if x = r then the tour is finished; otherwise, set x to the parent of x and continue.

Any sequence s obtained in this way is called a DFS order of the tree. Note that a tree T may have many DFS orders because the choice of which unvisited child to visit can vary.

Xiao A’s assistant provides a fee table \(\{w_i\}\) in \(\LaTeX\) (with indices from 1 to \(2(n-1)\)) and the following rule to compute the revenue of a full tour on a tree T with DFS order s:

• For each \(i\) from 1 to \(n\), consider the simple path (i.e. the unique path in T) from \(s_i\) to \(s_{(i \bmod n)+1}\) (note that \(s_{n+1} = s_1\)). In this path, do not count the starting node \(s_i\) but count the ending node \(s_{(i \bmod n)+1}\>.
• Let the total journey be broken into a sequence of node arrivals. When Xiao A arrives at a node for the \(j\)th time overall, he collects \(w_j\) gold coins. (Here the fee table is given as \(w_1, w_2, \dots, w_{2(n-1)}\); it can be shown that for every legal tree \(T\) the total number of arrivals is exactly \(2(n-1)\).)
• The revenue of the tour is defined as \(w(T,s) = \sum_{j=1}^{2(n-1)} w_j\).

The DFS order \(s\) is given as input. A tree \(T\) (with root r) is said to be legal if the given sequence \(s\) is one of its possible DFS orders. Two trees are considered different if either their roots are different or there exists an edge which is present in one tree but not in the other.

Your task is to compute the sum of \(w(T,s)\) over all legal trees \(T\) (modulo \(998244353\)).

Observation: It can be proved that for any legal tree \(T\) with DFS order \(s\), the sum of distances on the cycle formed by connecting \(s_1, s_2, \dots, s_n, s_1\) is always \(2(n-1)\). Moreover, one may show that the number of legal trees having a fixed DFS preorder \(s\) is exactly the \((n-1)\)th Catalan number \(C_{n-1}\). Hence, the answer may be computed as:

[ \text{Answer} = C_{n-1} \times \Biggl(\sum_{i=1}^{2(n-1)} w_i\Biggr) \mod 998244353. ]

Note that the DFS order s (a permutation of \(\{1, 2, \dots, n\}\)) is given and its first element is the capital (r). If the given sequence is not a valid DFS order (for example, if it is not a permutation or if the root is not in the first position), you may assume the input is invalid; however, in all test cases the input will be valid.

inputFormat

The input consists of three parts:

1. An integer n (1 ≤ n ≤ 105), the number of nodes.
2. A line with n distinct integers s1 s2 … sn representing the DFS order (a permutation of \(1,2,\dots, n\)). The first element s1 is the capital (the root).
3. A line with 2(n-1) integers: w1 w2 … w2(n-1), which is the fee table. (It is guaranteed that the total number of arrivals in the tour is exactly 2(n-1).)

outputFormat

Output a single integer, the sum of revenues \(w(T,s)\) over all legal trees \(T\), modulo 998244353.

sample

3
1 2 3
1 2 3 4

20