Po rozwiązaniu zadania Gem Island z finałów ACM-ICPC World Finals 2018, Little Cyan Fish uznał, że jest ono zbyt łatwe. Na szczęście dobry przyjaciel Little Cyan Fish, Little DrinkDrinkCongee, przygotował dla niego następujące zadanie. Chciałby on, abyś pomógł mu je rozwiązać.

W rzędzie znajduje się $n$ pudełek. Początkowo w każdym pudełku znajduje się dokładnie jedna kula. Wykonasz następującą operację dokładnie $d$ razy:

• Wybierz kulę $x$ spośród wszystkich kul jednostajnie losowo.
• Załóżmy, że kula $x$ znajduje się w pudełku $b$; dodaj jeszcze jedną kulę do pudełka $b$.

Najwyraźniej podczas $i$-tej operacji każda kula ma prawdopodobieństwo $\frac{1}{n+i-1}$ bycia wybraną. Załóżmy, że po $d$ operacjach liczby kul w tych $n$ pudełkach zostały uporządkowane w kolejności nierosnącej jako $a_1 \geq a_2 \geq \dots \geq a_n$. Znajdź wartość oczekiwaną $\sum_{i=1}^r a_i$ modulo $998\,244\,353$.

Ponieważ zadanie jest zbyt trudne dla Little Cyan Fish, poprosił cię o pomoc w jego rozwiązaniu.

Wejście

Pierwsza linia wejścia zawiera trzy liczby całkowite $n$, $d$ oraz $r$ ($1 \leq n, d \leq 1.5 \times 10^7$, $1 \leq r \leq n$).

Wyjście

Wypisz w jednej linii pojedynczą liczbę całkowitą, oznaczającą wynik modulo $998\,244\,353$.

Przykład

Wejście 1

2 3 1

Wyjście 1

499122180

Wejście 2

3 3 2

Wyjście 2

698771052

Wejście 3

5 10 3

Wyjście 3

176512750