AT_arc223_d.Xpectation of Cards in Hand with Laboratory

There are $A$ "draw" cards and $B$ normal cards. Among the $(A+B)!$ permutations of these $A+B$ cards, one is chosen uniformly at random, and the cards are stacked top to bottom in that order to form a deck. Then, $K$ cards are drawn from the top of the deck and placed in your hand. As long as your hand contains at least one draw card, repeat the following operation:

• Discard one draw card from your hand. The discarded card is removed from your hand and does not return to the deck.
• Let $c$ be the number of cards remaining in the deck. Add $\min(c,2)$ cards from the top of the deck to your hand.

Find the expected number, modulo $998244353$, of cards in your final hand.

Solve $T$ test cases per input.

Definition of modulo $998244353$

Under the constraints of this problem, it can be proved that the answer is a rational number, and that when it is expressed as an irreducible fraction $\frac{P}{Q}$, it satisfies $Q {{}\not\equiv{}} 0 \pmod{998244353}$. Thus, the integer $R$ satisfying $R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353$ is uniquely determined. Output this $R$.

有 $A$ 张“抽牌”和 $B$ 张普通牌。在这些 $A+B$ 张牌的 $(A+B)!$ 种排列中，等概率随机选择一种，并按该顺序自上而下叠放形成一副牌组。然后，从牌组顶部抽取 $K$ 张牌放入手牌中。只要手牌中至少含有一张抽牌，就重复执行以下操作：

• 从手牌中弃掉一张抽牌（该牌被移出手牌，不会回到牌组中）；
• 设此时牌组中剩余 $c$ 张牌，则从牌组顶部再抽取 $\min(c,2)$ 张牌加入手牌。

求最终手牌中牌的数量的期望值，结果对 $998244353$ 取模。

每组输入包含 $T$ 个测试用例，需全部求解。

模 $998244353$ 的定义：

在本题约束下，可以证明答案为一个有理数；且当其表示为既约分数 $\frac{P}{Q}$ 时，满足 $Q {{}\not\equiv{}} 0 \pmod{998244353}$。因此，满足 $R \times Q \equiv P \pmod{998244353}$ 且 $0 \leq R < 998244353$ 的整数 $R$ 是唯一确定的。请输出该 $R$。

The input is given from Standard Input in the following format:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case $\mathrm{case}_t$ is given in the following format:

$A$ $B$ $K$

输入从标准输入给出，格式如下：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例 $\mathrm{case}_t$ 的格式如下：

$A$ $B$ $K$

Output the answers over a total of $T$ lines. The $t$-th line should contain the answer for the $t$-th test case.

在总共 $T$ 行上输出答案。第 $t$ 行应包含第 $t$ 个测试用例的答案。

Sample 1 Explanation:
For the first test case, the initial hand always contains at least $1$ draw card, and the deck has $1$ card remaining. After performing the operation once, the hand contains $1$ draw card and $2$ normal cards. After performing the operation once more, the hand contains $0$ draw cards and $2$ normal cards.
For the second test case, the final hand size is $2$ if the first drawn card is a draw card, and $1$ if it is a normal card. The expected value is $\frac{1}{3} \times 2 + \frac{2}{3} \times 1 = \frac{4}{3}$.

Constraints

• $1 \leq T \leq 10^5$
• $1 \leq A, B$
• $1 \leq K \leq A+B \leq 10^7$
• The sum of $A+B$ over all test cases is at most $10^7$.
• All input values are integers.

样例 1 解释：
对于第一个测试用例，初始手牌中始终至少包含 $1$ 张抽牌，且牌堆中剩余 $1$ 张牌。执行一次操作后，手牌中包含 $1$ 张抽牌和 $2$ 张普通牌；再执行一次操作后，手牌中包含 $0$ 张抽牌和 $2$ 张普通牌。
对于第二个测试用例，若首次抽到的牌为抽牌，则最终手牌大小为 $2$；若首次抽到的牌为普通牌，则最终手牌大小为 $1$。期望值为 $\frac{1}{3} \times 2 + \frac{2}{3} \times 1 = \frac{4}{3}$。

约束条件

• $1 \leq T \leq 10^5$
• $1 \leq A, B$
• $1 \leq K \leq A+B \leq 10^7$
• 所有测试用例的 $A+B$ 之和不超过 $10^7$。
• 所有输入值均为整数。