시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 0 0 0 0.000%

문제

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

예제 입력 1

0 0 4

예제 출력 1

3

예제 입력 2

1 4 6

예제 출력 2

60

힌트

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