Vous disposez d'une suite de chiffres $1$ et $2$. En une étape, vous pouvez :

1. Insérer un $1$ à une position située à droite de tous les autres $1$ (ou n'importe où s'il n'y a aucun $1$).
2. Transformer un $2$ quelconque en $1$, s'il n'y a aucun $1$ à droite de ce $2$.
3. Supprimer le $1$ le plus à droite (remarquez que cette opération est l'inverse de l'opération 1).
4. Transformer le $1$ le plus à droite en $2$ (remarquez que cette opération est l'inverse de l'opération 2).

Par exemple, à partir de la suite $11212122$, vous pouvez obtenir les suites suivantes en une étape :

• Avec l'opération 1 : $112121122$, $112121212$, $112121221$.
• Avec l'opération 2 : $11212112$, $11212121$.
• Avec l'opération 3 : $1121222$.
• Avec l'opération 4 : $11212222$.

Votre tâche consiste à calculer le nombre de façons de transformer une suite composée d'exactement $a$ chiffres $2$ en une suite composée d'exactement $b$ chiffres $2$, en utilisant exactement $t$ opérations.

Entrée

L'unique ligne de l'entrée contient trois entiers $a$, $b$ et $t$ ($0 \le a,b,t \le 10^6$).

Sortie

Affichez le nombre de façons d'obtenir une suite de $b$ chiffres $2$ à partir d'une suite de $a$ chiffres $2$ en exactement $t$ étapes. Comme ce nombre peut être très grand, affichez-le modulo le nombre premier $998\,244\,353$.

Exemples

Entrée 1

0 0 4

Sortie 1

3

Entrée 2

1 4 6

Sortie 2

60

Remarque

Dans le premier exemple, vous devez obtenir une suite vide à partir d'une suite vide en 4 étapes. Les façons d'y parvenir sont les suivantes ($\varepsilon$ désigne la suite vide) :

$$\varepsilon \to 1 \to \varepsilon \to 1 \to \varepsilon$$

$$\varepsilon \to 1 \to 11 \to 1 \to \varepsilon$$

$$\varepsilon \to 1 \to 2 \to 1 \to \varepsilon$$