Problem Description

Bob has a generator which can generate a discrete probability distribution according to a given vector and a parameter.

This generator can be described as follows:

Now, given a vector $y[1..k]$, compute the probability density of the discrete probability distribution $y'[1..k]$ the algorithm output at the given vector $y[1..k]$. More specificly, compute the probability density $f_{GENERATE(x,k,t)}(y)$. Here, we see $GENERATE(x,k,t)$ as a random vector.

You should print the answers module $998244353$.

Input

The first line contains the only integer $T$ denoting the number of test cases.

Each of the following $T$ test cases begins with two integers $k$ and $t$ in the first line, $k$ intergers $x_i$ follow in the second line and $k$ intergers $z_i$ follow in the third line.

Here, you can compute $y_i$ by $y_i = z_i / \sum_{j} z_j$.

Note that $\sum k \le 10^6, k \in [2,10^6], t, x_i, z_i \in [1,998244353)$.

Output

For each test case, print the only integer in one line denoting the required probability density module $998244353$.

Note that we guarantee the answers always exsit, i.e., $\sum z_i$ $mod$ $998244353$ $\ne 0$.

2
3 1
1 1 1
2 2 2
3 2
1 1 1
1 2 3

2
596788047