There are N chits, out of which, A chits have 1 written on them and B (A+B = N) chits have 0 written on them.

Chef and Chefina are taking alternate turns. They both have a personal score which is initially set to 0. Chef starts first. On their turn, a player will:
Pick a random chit among the available chits;
Add the number written on the chit to their personal score;
Remove the chit that was picked.

Determine the [expected] score of Chef after all chits have been picked.

The expected score can be written in the form of \frac{P}{Q} such that Q is not divisible by 998244353 and its guaranteed that for testcases that Q is not a multiple of 998244353. Output the value of P \cdot Q^{-1} mod 998244353.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two integers A and B, the number of chits having 1 and 0 respectively.

------ Output Format ------ 

For each test case, output the expected score of Chef.  
The expected score can be written in the form of \frac{P}{Q}. Output the value of P \cdot Q^{-1} mod 998244353.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$0 ≤ A, B ≤ 10^{9}$
$1 ≤ A+B ≤ 10^{9}$

----- Sample Input 1 ------ 
3
1 1
0 5
3 4

----- Sample Output 1 ------ 
499122177
0
285212674

----- explanation 1 ------ 
Test case $1$: There is one chit with $1$ written on it and $1$ chit with $0$ written on it. Consider all possible cases as follows:
- Chef picks the chit with $1$ on his turn. Thus, Chefina picks the chit with $0$. The final score of Chef is $1$.
- Chef picks the chit with $0$ on his turn. Thus, Chefina picks the chit with $1$. The final score of Chef is $0$.

The expected score of Chef is $\frac {1}{2} \cdot 1 + \frac {1}{2} \cdot 0 = \frac {1}{2}$. This is equivalent to $1\cdot 2^{-1} = 499122177$.

Test case $2$: All chits have $0$ written on them. Thus, in any case, the final score would be $0$. Thus, the expected score of Chef is also $0$.

Difficulty: VERY_HARD
Tags: Combinatorics

Mathematics

Probability

Starter code:

Solutions:
import math
from fractions import Fraction
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	M = 998244353
	n = a + b
	p = Fraction(int(math.ceil(n / 2)), n)
	exp = a * p
	p = exp.numerator
	q = exp.denominator
	print(p * pow(q, -1, M) % M)


import math
from fractions import Fraction
M = 998244353

def solve(a, b):
	n = a + b
	p = Fraction(int(math.ceil(n / 2)), n)
	expected = a * p
	(p, q) = (expected.numerator, expected.denominator)
	return p * pow(q, -1, M) % M
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	print(solve(a, b))


mod = 998244353
for i in range(int(input())):
	(x, y) = map(int, input().split())
	ans = (x + y + 1) // 2 * pow(x + y, mod - 2, mod)
	print(ans * x % mod)


import math
t = int(input())
mod = 998244353
for _ in range(t):
	(a, b) = map(int, input().split())
	n = a + b
	print(math.ceil(n / 2) * a * pow(n, mod - 2, mod) % mod)


mod = 998244353
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	res = (a + b + 1) // 2 * pow(a + b, mod - 2, mod)
	print(res * a % mod)


MOD = 998244353
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	n = a + b
	k = (n + 1) // 2
	print(k * a * pow(n, MOD - 2, MOD) % MOD)


mod = 998244353
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	ans = (a + b + 1) // 2 * pow(a + b, mod - 2, mod)
	print(ans * a % mod)


MOD = 998244353

def expSum(a, b):
	n = a + b
	k = (n + 1) // 2
	n_inv = pow(n, MOD - 2, MOD)
	ans = a * k * n_inv % MOD
	return ans
t = int(input())
for _ in range(t):
	(ones, zeros) = [int(x) for x in input().split()]
	print(expSum(ones, zeros))


import sys, math

def _input():
	return sys.stdin.readline().strip()

def singleLineArr():
	return [int(n) for n in input().split()]

def mulLineArr(lineCnt):
	return [int(_input()) for _ in range(lineCnt)]
mod = 998244353

def solve(a, b):
	n = a + b
	return math.ceil(n / 2) * a * pow(n, mod - 2, mod) % mod
t = int(input())
for _ in range(t):
	(a, b) = singleLineArr()
	print(solve(a, b))


import math
mod = 998244353

def solve(a, b):
	n = a + b
	return math.ceil(n / 2) * a * pow(n, mod - 2, mod) % mod
t = int(input())
for _ in range(t):
	(a, b) = list(map(int, input().split()))
	print(solve(a, b))


MOD = 998244353
tests = int(input())
import math
for t0 in range(tests):
	(a, b) = map(int, input().split())
	n = a + b
	n1 = math.ceil(n / 2)
	n2 = math.floor((a + b) / 2)
	print(a * n1 * pow(n, -1, MOD) % MOD)


def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())
import math

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m
for t in range(int(input())):
	(a, b) = mi()
	n = a + b
	from math import ceil
	k = ceil(n / 2)
	print(modDivide(a * k, n, 998244353))


mod = 998244353

def helper(p, q):
	e = mod - 2
	while e:
		if e & 1:
			p = p * q % mod
		q = q * q % mod
		e = e >> 1
	return p
t = int(input())
while t > 0:
	(a, b) = map(int, input().split())
	k = (a + b + 1) // 2
	print(helper(k, a + b) * a % mod)
	t -= 1


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	n = a + b
	k = (n + 1) // 2
	print(k * a * pow(n, 998244351, 998244353) % 998244353)


def ans(a, b):
	if (a + b) % 2 == 0:
		return a * pow(2, 998244353 - 2, 998244353) % 998244353
	else:
		return a * ((a + b) // 2 + 1) * pow(a + b, 998244353 - 2, 998244353) % 998244353
for _ in range(int(input())):
	l = list(map(int, input().strip().split()))
	print(ans(l[0], l[1]) % 998244353)


for _ in range(int(input())):
	(A, B) = list(map(int, input().split()))
	P = (A + B + 1) // 2
	P *= A
	Q = A + B
	print(pow(Q, -1, 998244353) * P % 998244353)


test = int(input())
while test:
	mod = 998244353
	(a, b) = map(int, input().split())
	n = a + b
	k = (n + 1) // 2
	p1 = a % mod
	p2 = k % mod
	p3 = pow(n, -1, 998244353)
	print(p1 * p2 % mod * p3 % mod)
	test -= 1


from math import ceil
t = int(input())
for _ in range(t):
	(a, b) = [int(v) for v in input().split()]
	n = a + b
	(num, den) = (a * ceil(n / 2), n)
	den = pow(den, -1, 998244353)
	ans = num * den % 998244353
	print(ans)


T = int(input())
import math
P = 998244353

def binpow(x, n):
	if n == 0:
		return 1
	sub = binpow(x, n // 2)
	if n % 2:
		return sub * sub * x % P
	else:
		return sub * sub % P
for t in range(T):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	n = (a + b + 1) // 2
	numa = a * n
	deno = a + b
	dinv = binpow(deno, P - 2) % P
	print(numa * dinv % P)


def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def lsi():
	return si().strip().split(' ')

def ni():
	return int(input())
mod = 998244353
for _ in range(ni()):
	(a, b) = mi()
	ans = (a + b + 1) // 2 * pow(a + b, mod - 2, mod)
	print(ans * a % mod)


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	if (m + n) % 2 == 1:
		if min(m, n) == 0:
			print((m + 1) // 2 % 998244353)
		else:
			print(pow(m + n, 998244351, 998244353) * m * ((m + n) * 499122177 - 499122176) % 998244353)
	else:
		print(m * 499122177 % 998244353)


def inv(x):
	return pow(x, 998244351, 998244353)

def f(a, b):
	return a * inv(2) % 998244353
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if (a + b) % 2 == 1:
		if a == 0:
			print(0)
		elif b == 0:
			print((a + 1) // 2 % 998244353)
		else:
			print((a * inv(a + b) * (f(a - 1, b) + 1) + b * inv(a + b) * f(a, b - 1)) % 998244353)
	else:
		print(f(a, b))


import math
for i in range(int(input())):
	(a, b) = map(int, input().split())
	n = (a + b) // 2 + (a + b) % 2
	m = 998244353
	p = a * pow(a + b, m - 2, m) % m
	print(p * n % m)


import math
for _ in range(int(input())):
	(a, b) = [int(i) for i in input().split()]
	m = 998244353
	t = math.ceil((a + b) / 2)
	y = pow(a + b, -1, m)
	ans = a * t * y % m
	print(ans)


def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
t = int(input())
for cases in range(t):
	(a, b) = list(map(int, input().split()))
	if (a + b) % 2:
		turn = (a + b + 1) // 2
	else:
		turn = (a + b) // 2
	print(calculate(turn * a, a + b))


def ii():
	return int(input())

def li(c=int):
	return list(map(c, input().split()))

def lo(arr, sep=' '):
	arr = [str(i) for i in arr]
	print(sep.join(arr))

def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def solve():
	(a, b) = li()
	ct = (a + b) // 2 + (a + b) % 2
	print(calculate(ct * a, a + b))
for testcase in range(int(input())):
	solve()


import collections
import math
import random
import sys
from functools import *
from heapq import *
input = lambda : sys.stdin.readline().rstrip('\r\n')
ints = lambda : list(map(int, input().split()))
MOD = 998244353

def solve() -> None:
	(a, b) = map(int, input().split())
	n = a + b
	k = (n + 1) // 2
	print(k * a * pow(n, MOD - 2, MOD) % MOD)
t = int(input())
for _ in range(t):
	solve()


import math
beeg = 998244353
for tea in range(int(input())):
	(a, b) = map(int, input().split())
	n = a + b
	(p, q) = ((n + 1) // 2 * a, n)
	lawl = math.gcd(p, q)
	(p, q) = (p // lawl, q // lawl)
	print(p * pow(q, -1, beeg) % beeg)


M = 998244353

def solve():
	(a, b) = [int(x.strip()) for x in input().strip().split()]
	pO = a * pow(a + b, -1, M) % M
	if (a + b) % 2 == 0:
		ans = pO * (a + b) * pow(2, -1, M)
	else:
		ans = pO * (a + b + 1) * pow(2, -1, M)
	print(ans % M)
t = int(input())
for _ in range(t):
	solve()