Игра в ашыки
Айбек и Бекзат играют в ашыки (альчики). У Айбека a ашыков, у Бекзата — b. В каждом раунде Айбек выигрывает с вероятностью x / y и забирает один ашык у Бекзата, иначе Бекзат забирает один ашык у Айбека. Игра заканчивается, когда у кого-то из мальчиков не остаётся ни одного ашыка.
Найдите математическое ожидание числа раундов игры. Ответ — рациональное число P / Q; выведите P · Q⁻¹ по модулю 998244353.
Входные данные
В первой строке — число T (1 ≤ T ≤ 10⁵) — количество партий. В каждой из следующих T строк — четыре целых числа a b x y (1 ≤ a, b ≤ 10¹⁸, 1 ≤ x < y ≤ 10⁹).
Если 2x ≠ y, гарантируется, что число x^(a+b) − (y − x)^(a+b) не делится на 998244353.
Выходные данные
Для каждой партии выведите ожидаемое число раундов по модулю 998244353.
Пример 1
Вход:
3
1 1 1 3
2 3 1 2
1 2 2 3
Выход:
1
6
855638019
Пояснение
В первой партии у каждого по одному ашыку — игра длится ровно один раунд. Во второй шансы равны, и ожидание равно a · b = 6. В третьей у Айбека 1 ашык, у Бекзата 2, Айбек выигрывает раунд с вероятностью 2/3: ожидание равно 15/7.
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 15 % тестов a + b ≤ 15, ещё в 10 % тестов a, b ≤ 10⁹.
Комментарии