Олимпиадный тренинг

Задача . H. ZS тасует карты


У zscoder есть колода из \(n+m\) карт, изготовленная по индивидуальному заказу, которая состоит из \(n\) карт пронумерованных от \(1\) до \(n\) и \(m\) джокеров. Так как zscoder одинок, он хочет поиграть с сам с собой, используя эти карты.

Изначально колода перетасовывается в случайном порядке и кладется на стол. У zscoder есть изначально пустое множество \(S\).

Каждую секунду zscoder вытягивает верхнюю карту из колоды.

  • Если на карте написано число \(x\), zscoder снимает карту и добавляет \(x\) в множество \(S\).
  • Если извлеченная карта является джокером, zscoder помещает все карты обратно в колоду и перетасовывает (равномерно случайным образом) все \(n+m\) карт, получая новую колоду (следовательно, новая колода также содержит все карты от \(1\) до \(n\) и \(m\) джокеров). Затем, если \(S\) в настоящее время содержит все элементы от \(1\) до \(n\), игра заканчивается. Перетасовка колоды не занимает времени.

Какое матожидание количества секунд до окончания игры? Можно показать, что ответ можно записать в виде \(\frac{P}{Q}\), где \(P, Q\)  — взаимно простые целые числа, где \(Q \neq 0 \bmod 998244353\). Выведите значение \((P \cdot Q^{-1})\) по модулю \(998244353\).

Входные данные

Единственная строка содержит два целых числа, \(n\) и \(m\) (\(1 \le n, m \le 2 \cdot 10^{6}\)).

Выходные данные

Выведите единственное целое число, значение \((P \cdot Q^{-1})\) по модулю \(998244353\).

Примечание

Для первого примера можно доказать, что ожидаемое время до окончания игры составляет \(5\) секунд.

Для второго примера можно доказать, что ожидаемое время до окончания игры составляет \(\frac{28}{3}\)секунды.


Примеры
Входные данныеВыходные данные
1 2 1
5
2 3 2
332748127
3 14 9
969862773

time 2000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя