311159: CF1942G. Bessie and Cards

G. Bessie and Cardstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputSecond Dark Matter Battle - Pokemon Super Mystery Dungeon⠀

Bessie has recently started playing a famous card game. In the game, there is only one deck of cards, consisting of $a$ "draw $0$" cards, $b$ "draw $1$" cards, $c$ "draw $2$" cards, and $5$ special cards. At the start of the game, all cards are in the randomly shuffled deck.

Bessie starts the game by drawing the top $5$ cards of the deck. She may then play "draw $x$" cards from the hand to draw the next $x$ cards from the top of the deck. Note that every card can only be played once, special cards cannot be played, and if Bessie uses a "draw $2$" card when there is only $1$ card remaining in the deck, then she simply draws that remaining card. Bessie wins if she draws all $5$ special cards.

Since Bessie is not very good at math problems, she wants you to find the probability that she wins, given that the deck is shuffled randomly over all $(a + b + c + 5)!$ possible orderings. It can be shown that this answer can always be expressed as a fraction $\frac{p}{q}$ where $p$ and $q$ are coprime integers. Output $p \cdot q^{-1}$ modulo $998\,244\,353$.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case contains three integers $a$, $b$, and $c$ ($0 \le a, b, c \le 2 \cdot 10^5$) – the number of draw $0$ cards, draw $1$ cards, and draw $2$ cards, respectively.

It is guaranteed that the sum of $a$ over all test cases does not exceed $2 \cdot 10^5$, the sum of $b$ over all test cases does not exceed $2 \cdot 10^5$, and the sum of $c$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the probability that Bessie wins, modulo $998\,244\,353$.

ExampleInput

4
1 1 1
0 0 0
5 3 7
3366 1434 1234

Output

903173463
1
35118742
398952013

Note

In the first case, we have $1$ of each type of "draw" card and $5$ special cards. There are $30\,720$ starting decks where Bessie will win by drawing the top $5$ cards and $40\,320$ starting decks in total. Thus, the probability of Bessie winning is $\frac{30\,720}{40\,320} = \frac{16}{21}$.

One example of a winning starting deck is, top to bottom,

1. "Special",
2. "Draw $1$",
3. "Special",
4. "Special",
5. "Draw $0$",
6. "Draw $2$",
7. "Special",
8. "Special".

One example of a losing starting deck is:

1. "Special",
2. "Draw $1$",
3. "Special",
4. "Special",
5. "Draw $0$",
6. "Special",
7. "Special",
8. "Draw $2$".

题目大意：
Bessie 最近开始玩一款著名的纸牌游戏。在这个游戏中，只有一副牌，包含 $a$ 张“抽 0 张”的牌，$b$ 张“抽 1 张”的牌，$c$ 张“抽 2 张”的牌，以及 5 张特殊牌。游戏开始时，所有牌都是随机洗混的。

Bessie 通过抽取牌堆顶部的 5 张牌开始游戏。然后，她可以从手中打出“抽 $x$ 张”的牌，以从牌堆顶部抽取下一张 $x$ 张牌。注意，每张牌只能使用一次，特殊牌不能打出，如果 Bessie 在牌堆中只剩下一张牌时打出“抽 2 张”的牌，那么她只能抽取那张剩下的牌。如果 Bessie 抽取了所有 5 张特殊牌，她就赢了。

要求计算 Bessie 赢的概率，假设牌堆是随机洗混的，考虑所有 $(a + b + c + 5)!$ 种可能的排列。答案可以表示为分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是互质的整数。输出 $p \cdot q^{-1}$ 模 $998,244,353$。

输入输出数据格式：
输入：
- 第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。
- 每个测试用例包含三个整数 $a$、$b$ 和 $c$ ($0 \le a, b, c \le 2 \cdot 10^5$) —— 分别是“抽 0 张”的牌的数量、“抽 1 张”的牌的数量和“抽 2 张”的牌的数量。

输出：
- 对于每个测试用例，输出一个整数 —— Bessie 赢的概率，模 $998,244,353$。题目大意： Bessie 最近开始玩一款著名的纸牌游戏。在这个游戏中，只有一副牌，包含 $a$ 张“抽 0 张”的牌，$b$ 张“抽 1 张”的牌，$c$ 张“抽 2 张”的牌，以及 5 张特殊牌。游戏开始时，所有牌都是随机洗混的。 Bessie 通过抽取牌堆顶部的 5 张牌开始游戏。然后，她可以从手中打出“抽 $x$ 张”的牌，以从牌堆顶部抽取下一张 $x$ 张牌。注意，每张牌只能使用一次，特殊牌不能打出，如果 Bessie 在牌堆中只剩下一张牌时打出“抽 2 张”的牌，那么她只能抽取那张剩下的牌。如果 Bessie 抽取了所有 5 张特殊牌，她就赢了。 要求计算 Bessie 赢的概率，假设牌堆是随机洗混的，考虑所有 $(a + b + c + 5)!$ 种可能的排列。答案可以表示为分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是互质的整数。输出 $p \cdot q^{-1}$ 模 $998,244,353$。 输入输出数据格式： 输入： - 第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。 - 每个测试用例包含三个整数 $a$、$b$ 和 $c$ ($0 \le a, b, c \le 2 \cdot 10^5$) —— 分别是“抽 0 张”的牌的数量、“抽 1 张”的牌的数量和“抽 2 张”的牌的数量。 输出： - 对于每个测试用例，输出一个整数 —— Bessie 赢的概率，模 $998,244,353$。