|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||512 MB||0||0||0||0.000%|
You have a sequence of digits $1$ and $2$. In one step you can:
For example, you can obtain the following sequences in one step from the sequence 11212122:
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$.
0 0 4
1 4 6
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$$