Problem 3: Coin Tossing

Xiao A and Xiao B are good friends who often play together. Recently, Xiao B has become obsessed with a mobile game, grinding levels all day and neglecting his studies. Having played for several months without ever pulling an SSR character, he has become deeply disillusioned with life. Diligent Xiao A, wanting to persuade Xiao B to quit the game and focus on his studies, decides to use a coin-tossing game to show Xiao B that he is truly unlucky, hoping to make him lose hope in the game. Both of them toss a coin $b$ times. If the number of times Xiao A's coin lands on heads is greater than the number of times Xiao B's coin lands on heads, Xiao A wins.

In reality, Xiao A was also once obsessed with a rhythm game and never pulled a UR character either, so he is not very confident in his own luck. Therefore, he decides to cheat when Xiao B is not paying attention by secretly tossing his coin a few extra times. Of course, to avoid suspicion, he will not toss it too many times. Now, Xiao A wants to ask you: in how many possible scenarios can he defeat Xiao B? Since the answer can be very large, you only need to output the last $k$ digits of the answer in decimal representation.

Input

The input contains multiple test cases. For each test case, input three integers $a, b, k$, representing the number of times Xiao A tosses the coin, the number of times Xiao B tosses the coin, and the number of digits to keep for the final answer, respectively.

Output

For each test case, output a single integer representing the last $k$ digits of the final answer. If the result has fewer than $k$ digits, pad it with leading zeros.

Constraints

• $10\%$ of the data satisfies $a, b \le 20$.
• $30\%$ of the data satisfies $a, b \le 100$.
• $70\%$ of the data satisfies $a, b \le 100\,000$, among which $20\%$ of the data satisfies $a = b$.
• $100\%$ of the data satisfies $1 \le a, b \le 10^{15}$, $b \le a \le b + 10\,000$, $1 \le k \le 9$.
• The number of test cases is at most $10$.

Examples

Input 1

2 1 9
3 2 1

Output 1

000000004
6

Note

For the first test case, when Xiao A tosses the coin 2 times and Xiao B tosses the coin 1 time, there are 4 scenarios where the number of heads for Xiao A is greater than that for Xiao B: (01,0), (10,0), (11,0), (11,1)

For the second test case, when Xiao A tosses the coin 3 times and Xiao B tosses the coin 2 times, there are 16 scenarios where the number of heads for Xiao A is greater than that for Xiao 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)