20593번 - Easy One 출처다국어

You have a sequence of digits $1$ and $2$. In one step you can:

1. Insert $1$ in a place which is to the right of every other $1$ (or anywhere if there are no $1$s).
2. Transform any $2$ into $1$, if there are no $1$s to the right of this $2$.
3. Delete the rightmost $1$ (note that this operation is inverse to the operation 1).
4. Transform the rightmost $1$ into $2$ (note that this operation is inverse to the operation 2).

For example, you can obtain the following sequences in one step from the sequence 11212122:

• With operation 1: 112121122, 112121212, 112121221.
• With operation 2: 11212112, 11212121.
• With operation 3: 1121222.
• With operation 4: 11212222.

Your task is to calculate the number of ways to transform a sequence of exactly $a$ digits $2$ to a sequence of exactly $b$ digits $2$, using exactly $t$ operations.

The only line of the input contains three integers $a$, $b$, and $t$ ($0 \le a, b, t \le 10^6$).

Output the number of ways to obtain a sequence of $b$ digits $2$ from a sequence of $a$ digits $2$ in exactly $t$ steps. As this number can be very large, output it modulo prime number $998\,244\,353$.

In the first sample you should obtain an empty sequence from an empty sequence in 4 steps. Ways to do this are ($\varepsilon$ stands for empty sequence):

$$\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$$