Considérons des chaînes composées des parenthèses « ( » et « ) ». Les séquences de parenthèses régulières sont les chaînes qui peuvent être obtenues par les règles suivantes :

• La chaîne vide est une séquence de parenthèses régulière.
• Si $A$ est une séquence de parenthèses régulière, alors $(A)$ est une séquence de parenthèses régulière.
• Si $A$ et $B$ sont des séquences de parenthèses régulières, alors la concaténation de $A$ et $B$ est une séquence de parenthèses régulière.

Vous disposez de $N$ boîtes numérotées $1, 2, \dots, N$, ainsi que de deux entiers, $M$ et $K$. Votre tâche consiste à placer exactement une séquence de parenthèses régulière dans chacune des $N$ boîtes de telle sorte que les conditions suivantes soient remplies :

• Le nombre total de parenthèses « ( » dans l'ensemble des $N$ boîtes est égal à $M$.
• Les séquences de parenthèses régulières de longueur $2 \cdot K$ ne peuvent pas être placées dans les boîtes.

Comptez le nombre de manières différentes de procéder. Deux distributions sont considérées comme différentes s'il existe un nombre $i$ tel que la boîte $i$ contienne des séquences de parenthèses régulières différentes dans ces distributions.

Comme la réponse peut être très grande, affichez la réponse modulo $998\,244\,353$.

Entrée

L'entrée contient une ligne avec trois entiers $N$, $M$ et $K$ ($1 \le M, N \le 10^6$, $1 \le K \le M$).

Sortie

Affichez la réponse modulo $998\,244\,353$.

Exemples

Entrée 1

2 2 1

Sortie 1

4

Entrée 2

1 1 1

Sortie 2

0

Entrée 3

24 120 30

Sortie 3

379268651

Remarque

Pour le premier exemple, les distributions suivantes respectent les conditions :

• $(())$, vide ;
• $()()$, vide ;
• vide, $(())$ ;
• vide, $()()$.

Ainsi, la réponse est 4.