У 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\).
Выходные данные
Выведите единственное целое число, значение \((P \cdot Q^{-1})\) по модулю \(998244353\).
Примечание
Для первого примера можно доказать, что ожидаемое время до окончания игры составляет \(5\) секунд.
Для второго примера можно доказать, что ожидаемое время до окончания игры составляет \(\frac{28}{3}\)секунды.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
|
5
|
|
2
|
3 2
|
332748127
|
|
3
|
14 9
|
969862773
|