Description

Jiutiao Kelian is playing a very interesting strategy game: Slay the Spire. At the beginning, her deck contains $2n$ cards. Each card has a number $w_i$ written on it. There are two types of cards, with $n$ cards of each type:

1. Attack cards: After playing one, it deals damage equal to the number on the card.

2. Buff cards: After playing one, suppose the number on this buff card is $x$. Then the numbers on all remaining attack cards will be multiplied by $x$. It is guaranteed that the numbers on buff cards are all greater than 1.

Now Jiutiao Kelian will randomly draw $m$ cards from the deck with equal probability. Due to energy limits, she can play at most $k$ cards. Assume she always uses the strategy that can deal the maximum damage. Find the expected damage she can deal.

Suppose the answer is $\text{ans}$. You only need to output

$$\left (\text{ans}\times \frac{(2n)!}{m!(2n-m)!}\right) ~\bmod 998244353$$

Here, $x!$ means $\prod_{i=1}^{x}i$. In particular, $0!=1$.

Input Format

The first line contains a positive integer $T$, denoting the number of test cases.

For each test case:

The first line contains three positive integers $n,m,k$.

The second line contains $n$ positive integers $w_i$, representing the values on each buff card.

The third line contains $n$ positive integers $w_i$, representing the values on each attack card.

Output Format

Output $T$ lines. Each line contains a non-negative integer, representing the answer for each test case.

2
2 3 2
2 3
1 2
10 16 14
2 3 4 5 6 7 8 9 10 11
1 2 3 4 5 6 7 8 9 10

19
253973805

Hint

Sample Explanation

For example, Jiutiao Kelian draws attack cards $\{1,2\}$ and a buff card $\{3\}$. The optimal strategy is to play the buff card $3$ first. Then the values of the attack cards become $\{3,6\}$, and then she plays $6$.

Constraints

For all testdata, $1\leq k\leq m\leq 2n\leq 3000$, and $1\leq w_i\leq 10^8$.

It is guaranteed that the numbers on buff cards are all greater than 1.

Let $(\sum 2n)$ denote the sum of $2n$ over all test cases in the input.

For $10\%$ of the testdata, $1\leq \sum 2n\leq 10$.

For $20\%$ of the testdata, $1\leq \sum 2n\leq 100$.

For $30\%$ of the testdata, $1\leq \sum 2n\leq 500$.

For another $20\%$ of the testdata, all attack cards have the same value.

For another $20\%$ of the testdata, $m=k$.

For $100\%$ of the testdata, $1\leq \sum 2n\leq 3000$.

Translated by ChatGPT 5