Продвигаясь в своем пути к становлению математиком, Сервал стал студентом математического Университета Джапари. На уроке математики учитель научил его вычислять математическое ожидание длины случайного подотрезка данного отрезка. Затем он оставил бонусную задачу в качестве домашнего задания. Эта бонусная задача — расширить разобранную задачу на произвольный случай, как описано ниже.
Задан отрезок длиной \(l\). Мы случайным образом выбираем \(n\) отрезков, выбирая равновероятно две точки (возможно, с нецелыми координатами) из данного отрезка и получая отрезок между двумя этими точками. Вам дано количество случайных отрезков \(n\) и еще одно целое число \(k\). \(2n\) концов выбранных отрезков делят исходный отрезок на \((2n+1)\) отрезков. Ваша задача — вычислить математическое ожидание суммарной длины тех из отрезков, которые покрыты хотя бы \(k\) отрезками из \(n\) случайных отрезков.
Вам требуется вычислить ответ на эту задачу по модулю \(998244353\).
Выходные данные
Выведите одно целое число — математическое ожидание суммарной длины всех отрезков, покрытых хотя бы \(k\) отрезками из \(n\) случайных отрезков по модулю \(998244353\).
Формально, пусть \(M = 998244353\). Можно показать, что ответ может быть представлен в виде несократимой дроби \(\frac{p}{q}\), где \(p\) и \(q\) — целые числа, и \(q \not \equiv 0 \pmod{M}\). Выведите целое число, равное \(p \cdot q^{-1} \bmod M\). Другими словами, выведите такое целое число \(x\), что \(0 \le x < M\) и \(x \cdot q \equiv p \pmod{M}\).
Примечание
В первом примере математическое ожидание равно \(\int_0^1 \int_0^1 |x-y| \,\mathrm{d}x\,\mathrm{d}y = {1\over 3}\), а \(3^{-1}\) по модулю \(998244353\) равно \(332748118\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1 1
|
332748118
|
|
2
|
6 2 1
|
760234711
|
|
3
|
7 5 3
|
223383352
|
|
4
|
97 31 9984524
|
267137618
|