AT_arc223_d [ARC223D] Xpectation of Cards in Hand with Laboratory

ドローカード $ A $ 枚と普通のカード $ B $ 枚があります。 これら $ A+B $ 枚のカードからなる順列は $ (A+B)! $ 通りありますが、そのうちの $ 1 $ つを一様ランダムに選び、その順番に上下に積み重ねて山札とします。 そして山札の上から $ K $ 枚を引き、手札にします。 手札にドローカードが $ 1 $ 枚以上ある限り、以下の操作を繰り返します。 - 手札にあるドローカードを $ 1 $ 枚捨てる。捨てたカードは手札からなくなり、山札にも戻らない。 - 山札にあるカードの枚数を $ c $ として、山札の上から $ \min(c,2) $ 枚のカードを手札に加える。 最終的な手札のカード枚数の期待値を $ \text{mod } 998244353 $ で求めてください。 $ 1 $ つの入力につき、 $ T $ 個のテストケースを解いてください。 $ \text{mod } {998244353} $ の定義この問題の制約のもとでは、求める答えは有理数であることが証明でき、さらにこれを既約分数 $ \frac{P}{Q} $ で表した時、 $ Q {{}\not\equiv{}} 0 \pmod{998244353} $ となることが証明できます。 よって、 $ R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 $ を満たす整数 $ R $ が一意に定まります。 この $ R $ を答えてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケース $ \mathrm{case}_t $ は以下の形式で与えられる。 > $ A $ $ B $ $ K $

答えを合計 $ T $ 行で出力せよ。 $ t $ 行目には、 $ t $ 番目のテストケースの答えを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースでは、最初の手札にドローカードが必ず $ 1 $ 枚以上あり、山札にあるカードの枚数は $ 1 $ 枚です。 操作を $ 1 $ 回行うと手札にはドローカードが $ 1 $ 枚と普通のカードが $ 2 $ 枚あることになります。 もう一度操作を行って手札にはドローカードが $ 0 $ 枚と普通のカードが $ 2 $ 枚ある状態になります。 $ 2 $ つ目のテストケースでは、最初に引くカードがドローカードと普通のカードの場合で最終的な手札の枚数はそれぞれ $ 2,1 $ 枚となります。期待値は $ \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 $ - すべてのテストケースにおける $ A+B $ の総和は $ 10^7 $ 以下 - 入力される値はすべて整数