I. Random Tree Leaves
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integer sequences: $$$[a_1, a_2, \ldots , a_{n-1}]$$$ and $$$[c_1, c_2, \ldots , c_n]$$$.

You build a random rooted tree $$$T_n$$$ with vertex set $$${1, 2, \ldots , n}$$$ as follows:

  • Initially, $$$T_n$$$ consists of only vertex $$$1$$$ which is the root.
  • For each $$$i = 2, 3, \ldots , n$$$, we add vertex $$$i$$$ and connect it by an edge to exactly one vertex $$$j \in \{1, 2, ... , i−1\}$$$. The vertex $$$j$$$ is chosen randomly with probability $$$\frac{a_j}{a_1 + a_2 + \ldots + a_{i-1}}$$$.
  • When $$$T_n$$$ is built, the process stops.

Let $$$$$$F = \sum_{i \in S}{c_i}$$$$$$

where $$$S$$$ is the set of leaf vertices$$$^{\text{∗}}$$$ in $$$T_n$$$.

Find the expected value of $$$F$$$.

$$$^{\text{∗}}$$$A vertex is a leaf if it is not the root and its degree in $$$T_n$$$ equals to $$$1$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case is described as follows.

The first line contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of vertices in the tree $$$T_n$$$.

The second line contains $$$n-1$$$ integers $$$a_1, a_2, \ldots, a_{n-1}$$$ ($$$1 \le a_i \lt 998\,244\,353$$$).

For every test case, and for every $$$k$$$ with $$$1 \le k \le n-1$$$, the prefix sum $$$$$$ a_1 + a_2 + \dots + a_k \not\equiv 0 \pmod{998\,244\,353}. $$$$$$

The third line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, print a single integer — the expected value of $$$$$$ F = \sum_{i \in S} c_i, $$$$$$ where $$$S$$$ is the set of leaf vertices.

Since the expected value can be a fraction, output it modulo $$$998\,244\,353$$$.

Example
Input
4
3
5 1
2 1 6
2
5
1 8
8
10 7 4 1 10 1 2
9 6 4 6 5 8 3 5
2
5
9 5
Output
831870301
8
334205461
5
Note

In the first test case, vertex $$$2$$$ will have vertex $$$1$$$ as its parent. There is a $$$\frac{a_2}{a_1+a_2}$$$ = $$$\frac{1}{5+1}$$$ probability that the parent of vertex $$$3$$$ is vertex $$$2$$$, and a $$$\frac{a_1}{a_1+a_2}$$$ = $$$\frac{5}{5+1}$$$ probability that the parent is vertex $$$1$$$.

Hence, the expected value of $$$F$$$ is $$$$$$ \frac{1}{6} \cdot c_3 + \frac{5}{6} \cdot (c_2 + c_3) = \frac{1}{6} \cdot 6 + \frac{5}{6} \cdot (1 + 6) = \frac{41}{6}. $$$$$$