Bạn có một dãy gồm các chữ số $1$ và $2$. Trong một bước, bạn có thể:

1. Chèn một chữ số $1$ vào vị trí nằm bên phải mọi chữ số $1$ khác (hoặc vào bất kỳ đâu nếu không có chữ số $1$ nào).
2. Biến một chữ số $2$ bất kỳ thành $1$, nếu không có chữ số $1$ nào ở bên phải chữ số $2$ đó.
3. Xóa chữ số $1$ ngoài cùng bên phải (lưu ý rằng thao tác này là thao tác ngược của thao tác 1).
4. Biến chữ số $1$ ngoài cùng bên phải thành $2$ (lưu ý rằng thao tác này là thao tác ngược của thao tác 2).

Ví dụ, từ dãy $11212122$, bạn có thể thu được các dãy sau trong một bước:

• Với thao tác 1: $112121122$, $112121212$, $112121221$.
• Với thao tác 2: $11212112$, $11212121$.
• Với thao tác 3: $1121222$.
• Với thao tác 4: $11212222$.

Nhiệm vụ của bạn là tính số cách biến một dãy gồm đúng $a$ chữ số $2$ thành một dãy gồm đúng $b$ chữ số $2$, bằng đúng $t$ thao tác.

Dữ liệu vào

Dòng duy nhất của dữ liệu vào chứa ba số nguyên $a$, $b$ và $t$ ($0 \le a,b,t \le 10^6$).

Dữ liệu ra

In số cách thu được một dãy gồm $b$ chữ số $2$ từ một dãy gồm $a$ chữ số $2$ trong đúng $t$ bước. Vì số này có thể rất lớn, hãy in phần dư của nó khi chia cho số nguyên tố $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

0 0 4

Dữ liệu ra 1

3

Dữ liệu vào 2

1 4 6

Dữ liệu ra 2

60

Ghi chú

Trong ví dụ thứ nhất, bạn cần thu được dãy rỗng từ dãy rỗng trong 4 bước. Các cách thực hiện như sau ($\varepsilon$ biểu thị dãy rỗng):

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