Random Card Draw Strategy Optimization

You are given a deck of \(2n\) cards consisting of two types, each with \(n\) copies:

• Attack cards: When played, an attack card deals damage equal to the number written on it.
• Boost cards: When played, if its number is \(x\) (with \(x>1\)), it multiplies the numbers on all the other attack cards that remain to be played by \(x\).

The game proceeds as follows. First, exactly \(m\) cards are drawn uniformly at random from the deck. Then, due to cost constraints, the player may play at most \(k\) cards from the drawn set. The player always chooses a strategy to maximize the total damage dealt. Note that the player may choose the order of playing; the optimal strategy is to play some boost cards first (so that they multiply subsequent attack damage) and then an appropriate number of attack cards.

Suppose that in the drawn set the number of attack cards is \(A\) and that of boost cards is \(B\). After sorting the attack cards in descending order (largest damage first) and boost cards in descending order (largest multiplier first), an optimal strategy is as follows. For an integer \(r\) with \(0 \le r \le \min(B, k-1)\) (we must play at least one attack card so that \(k-r \ge 1\)), the player plays the top \(r\) boost cards and then plays the top \(\min(A, k-r)\) attack cards. The resulting damage is

[ \text{Damage} = \left(\prod_{i=1}^{r} x_i\right) \times \left(\sum_{j=1}^{\min(A,k-r)} a_j\right), ]

where (x_i) are the chosen boost multipliers and (a_j) are the chosen attack values. The maximum damage for those drawn cards is the maximum over all valid choices of (r).

Your task is to compute the expected maximum damage over all possible drawn subsets of size \(m\). However, instead of outputting the expected damage, let the answer be \(ans\) and output

[ \Bigl(ans \times \frac{(2n)!}{m!,(2n-m)!}\Bigr) \bmod 998244353. ]

In other words, if \(f(S)\) is the maximum damage achievable for drawn subset \(S\) then you are to compute

[ \sum_{S:|S|=m} f(S) \bmod 998244353. ]

Note: It is guaranteed that all boost card numbers are greater than 1. For the purposes of this problem, the constraints are small so that a brute force enumeration over the \(\binom{2n}{m}\) subsets is feasible.

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\).

The second line contains \(n\) space-separated integers representing the damage values of the attack cards.

The third line contains \(n\) space-separated integers representing the multipliers of the boost cards (each greater than 1).

outputFormat

Output a single integer: the sum over all subsets of \(m\) drawn cards of the maximum damage achievable (using at most \(k\) cards played in the optimal order), modulo \(998244353\). This is equivalent to \(\Bigl(ans \times \frac{(2n)!}{m!\,(2n-m)!}\Bigr) \bmod 998244353\) where \(ans\) is the expected damage.

sample

2 2 2
3 1
2 2

10