4468. 杀戮尖塔

【题目背景】

我是尖塔最强机器人！

【题目描述】

九条可怜在玩一个很好玩的策略游戏：Slay the Spire，一开始九条可怜的卡组里有 \(2n\) 张牌，每张牌上都写着一个数字\(w_i\)，一共有两种类型的牌，每种类型各 \(n\) 张：

1. 攻击牌：打出后对对方造成等于牌上的数字的伤害。
2. 强化牌：打出后，假设该强化牌上的数字为 \(x\)，则其他剩下的攻击牌的数字都会乘上 \(x\)。保证强化牌上的数字都大于 1。

现在九条可怜会等概率随机从卡组中抽出 \(m\) 张牌，由于费用限制，九条可怜最多打出 \(k\) 张牌，假设九条可怜永远都会采取能造成最多伤害的策略，求她期望造成多少伤害。

假设答案为 \(\text{ans}\) ，你只需要输出 \[ \left (\text{ans}\times \frac{(2n)!}{m!(2n-m)!}\right) ~\bmod 998244353 \] 即可。其中 \(x!\) 表示 \(\prod_{i=1}^{x}i\)，特别地，\(0!=1\) 。

【输入格式】

第一行一个正整数 \(T\) 表示数据组数
接下来对于每组数据：
第一行三个正整数 \(n,m,k\)
第二行 \(n\) 个正整数 \(w_i\)，表示每张强化牌上的数值。
第三行 \(n\) 个正整数 \(w_i\)，表示每张攻击牌上的数值。

【输出格式】

输出 \(T\) 行，每行一个非负整数表示每组数据的答案。

【样例输入】

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

【样例说明】

例如九条可怜抽到了攻击牌 \(\{1,2\}\) 和强化牌 \(\{3\}\)，那最优策略是先用掉强化牌 \(3\)，此时攻击牌的数值变成 \(\{3,6\}\)，然后打出 \(6\)。

【数据规模与约定】

对于所有数据，有 \(1\leq k\leq m\leq 2n\leq 3000\)，且\(1\leq w_i\leq 10^8\)。 保证强化牌上的数字都大于 1。
以下 \((\sum 2n)\) 表示对于输入中所有数据的\(2n\)的和。
对于 \(10\%\) 的数据，有 \(1\leq \sum 2n\leq 10\)
对于 \(20\%\) 的数据，有 \(1\leq \sum 2n\leq 100\)
对于 \(30\%\) 的数据，有 \(1\leq \sum 2n\leq 500\)
另有 \(20\%\) 的数据，满足所有攻击牌的数值相同。
另有 \(20\%\) 的数据，满足 \(m=k\)。
对于 \(100\%\) 的数据，有 \(1\leq \sum 2n\leq 3000\)

【来源】

[PKUWC2018] Slay the Spire