Description

A and B are good friends who often play together. Recently, B has been addicted to a mobile gacha game, grinding every day and not studying at all. After several months, he has never drawn an SSR, which makes him doubt life. The diligent A wants to persuade B to quit the game and study, so he decides to use coin tossing to show B that he is thoroughly unlucky. They would toss coins at the same time; if the number of heads A gets is greater than the number of heads B gets, then A wins.

However, A was also once addicted to a gacha game and has never drawn a UR, so he is not confident in his luck. He decides to cheat by secretly tossing a few extra times; to avoid suspicion, he will not toss too many extra times. Let $a$ be the total number of times A tosses, and $b$ be the total number of times B tosses. In how many possible outcomes can A defeat B? Since the answer can be large, you only need to output the last $k$ digits in decimal.

Input Format

Multiple test cases. For each test case, input three integers $a, b, k$, representing the number of times A tosses, the number of times B tosses, and how many digits of the final answer to keep.

Output Format

For each test case, output one number: the last $k$ digits of the answer. If it has fewer than $k$ digits, pad with leading zeros.

2 1 9
3 2 1

000000004
6

Hint

For the first test case, when A tosses $2$ times and B tosses $1$ time, there are $4$ favorable outcomes in which A gets more heads than B. $(01, 0), (10, 0), (11, 0), (11, 1)$.

For the second test case, when A tosses $3$ times and B tosses $2$ times, there are $16$ favorable outcomes in which A gets more heads than B. $(001, 00), (010, 00), (100, 00), (011, 00), (101, 00), (110, 00), (111, 00), (011, 01)$ $(101, 01), (110, 01), (111, 01), (011, 10), (101, 10), (110, 10), (111, 10), (111, 11)$.

Constraints

$10\%$ of the testdata satisfies $a, b \le 20$.

$30\%$ of the testdata satisfies $a, b \le 100$.

$70\%$ of the testdata satisfies $a, b \le 10^5$, among which $20\%$ satisfies $a = b$.

$100\%$ of the testdata satisfies $1 \le a, b \le 10^{15}$, $b \le a \le b + 10^4$, $1 \le k \le 9$, and the number of test cases is at most $10$.

Translated by ChatGPT 5