Имеется $N$ коробок, пронумерованных целыми числами от $1$ до $N$. Кроме того, для каждого целого числа от $1$ до $N$ есть $M$ шаров, помеченных этим числом.
Эти $NM$ шаров перемешиваются, а затем распределяются по $N$ коробкам так, что в каждой коробке оказывается ровно $M$ шаров.
Существует $\frac{(NM)!}{(M!)^N}$ способов размещения шаров (если считать все шары различимыми), и все эти варианты равновероятны.
Вы выполняете операции с этими коробками и шарами. Одна операция состоит из следующих шагов:
- Выберите любую коробку и встаньте перед ней.
- Если в этой коробке нет шаров, завершите операцию.
- Выберите любой шар из этой коробки и выбросьте его за пределы коробки.
- Наконец, перейдите к коробке, номер которой совпадает с номером только что выброшенного шара, и вернитесь к шагу 2.
Определим ваш счет как количество операций, потребовавшихся для того, чтобы все $NM$ шаров были выброшены. Вы хотите минимизировать этот счет.
Найдите математическое ожидание этого счета при оптимальной стратегии по модулю 998244353.
Входные данные
В первой строке содержатся числа $N$ и $M$ в указанном порядке, разделенные пробелами ($1 \le N \le 10^5$, $1 \le M \le 100$).
Выходные данные
Выведите ответ.
Определение математического ожидания по модулю 998244353
Можно доказать, что искомое математическое ожидание всегда является рациональным числом. Кроме того, при заданных ограничениях, если представить математическое ожидание в виде несократимой дроби $\frac{y}{x}$, гарантируется, что $x$ не делится на $998244353$.
В этом случае существует единственное целое число $z$ в диапазоне от $0$ до $998244352$ включительно, такое что $xz \equiv y \pmod{998244353}$. Выведите это число $z$.
Примеры
Входные данные 1
2 2
Выходные данные 1
166374060
Входные данные 2
3 1
Выходные данные 2
831870296
Входные данные 3
100000 100
Выходные данные 3
402978825
Примечание
Для первого примера возможные варианты распределения шаров и соответствующие оптимальные способы выполнения операций выглядят следующим образом:
Поместить два шара с номером 1 в коробку 1 и два шара с номером 2 в коробку 2. (Вероятность 1/6)
- В первой операции встаньте перед коробкой 1. Оттуда возьмите шар с номером 1 и встаньте перед коробкой 1. Затем возьмите еще один шар с номером 1 и снова встаньте перед коробкой 1. В этот момент коробка 1 пуста, поэтому завершите операцию.
- Во второй операции встаньте перед коробкой 2. Оттуда возьмите шар с номером 2 и встаньте перед коробкой 2. Затем возьмите еще один шар с номером 2 и снова встаньте перед коробкой 2. В этот момент коробка 2 пуста, поэтому завершите операцию.
- В этом случае минимально достижимый счет равен 2.
Поместить по одному шару с номером 1 и по одному шару с номером 2 в каждую из коробок 1 и 2. (Вероятность 2/3)
- В первой операции встаньте перед коробкой 1. Оттуда возьмите шар с номером 1 и встаньте перед коробкой 1. Затем возьмите шар с номером 2 и встаньте перед коробкой 2. Затем возьмите шар с номером 2 и встаньте перед коробкой 2. Затем возьмите шар с номером 1 и встаньте перед коробкой 1. В этот момент коробка 1 пуста, поэтому завершите операцию.
- В этом случае минимально достижимый счет равен 1.
Поместить два шара с номером 2 в коробку 1 и два шара с номером 1 в коробку 2. (Вероятность 1/6)
- В первой операции встаньте перед коробкой 1. Оттуда возьмите шар с номером 2 и встаньте перед коробкой 2. Затем возьмите шар с номером 1 и встаньте перед коробкой 1. Затем возьмите шар с номером 2 и встаньте перед коробкой 2. Затем возьмите шар с номером 1 и встаньте перед коробкой 1. В этот момент коробка 1 пуста, поэтому завершите операцию.
- В этом случае минимально достижимый счет равен 1.
Таким образом, минимальный счет равен 2 с вероятностью 1/6 и 1 с вероятностью 5/6, поэтому математическое ожидание счета в целом равно 7/6. Следовательно, выводим 166374060, что представляет это значение по модулю 998244353.