После решения задачи Gem Island с финала чемпионата мира ACM-ICPC 2018 года, Little Cyan Fish посчитал, что эта задача слишком проста. К счастью, хороший друг Little Cyan Fish, Little DrinkDrinkCongee, подготовил для него следующую задачу. Итак, он хотел бы решить следующую задачу.

Имеется $n$ коробок, стоящих в ряд. Изначально в каждой коробке находится ровно один шар. Вы должны выполнить следующую операцию ровно $d$ раз:

• Равномерно случайным образом выберите шар $x$ из всех имеющихся шаров.
• Предположим, что шар $x$ находится в коробке $b$, тогда добавьте еще один шар в коробку $b$.

Очевидно, что во время $i$-й операции каждый шар имеет вероятность $\frac{1}{n+i-1}$ быть выбранным. Предположим, что после $d$ операций количество шаров в этих $n$ коробках записано в невозрастающем порядке как $a_1 \ge a_2 \ge \dots \ge a_n$. Найдите математическое ожидание $\sum_{i=1}^r a_i$ по модулю $998\,244\,353$.

Поскольку задача слишком сложна для Little Cyan Fish, он попросил вас помочь ему решить её.

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

Первая строка входных данных содержит три целых числа $n$, $d$ и $r$ ($1 \le n, d \le 1.5 \times 10^7$, $1 \le r \le n$).

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

Выведите одну строку, содержащую единственное целое число — ответ по модулю $998\,244\,353$.

Примеры

Пример 1

2 3 1

499122180

Пример 2

3 3 2

698771052

Пример 3

5 10 3

176512750