Problem Description

Xiao Lan has $n$ white balls and $m$ black balls.

In each operation, Xiao Lan randomly selects 5 balls with equal probability. For the 5 selected balls, Xiao Lan dyes all of them into the color that appears most among these 5 balls. Find the probability that after $k$ rounds, all balls are of the same color. Output the answer modulo $998244353$.

Input Format

Input one line containing three non-negative integers $n, m, k$, separated by one space.

Output Format

Output one line containing one integer representing the answer.

Since the answer may be in the form $\dfrac{P}{Q}$, you need to output $P \cdot Q^{-1} \mod 998244353$, where $Q^{-1} \cdot Q \equiv 1 \pmod{998244353}$.

1 5 2

138645050

5 5 10

776052319

Hint

Sample Explanation 1

The answer for this sample, written as a fraction, is $\dfrac{35}{36}$.

Constraints and Notes

For $30\%$ of the testdata, $n + m \le 10$, $k \le 5$.

For $60\%$ of the testdata, $n + m \le 300$.

For all testdata, $n \ge 0$, $m \ge 0$, $5 \le n + m \le 5000$, $1 \le k \le 5000$.

Translated by ChatGPT 5