AT_arc223_d [ARC223D] 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 $ .

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 $

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

### Sample Explanation 1 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.