Cheating Coin Toss Showdown

Little A and Little B are close friends who often play games together. Recently, Little B has been obsessed with a mobile gacha game and spends every day grinding, yet not once has he managed to get an SSR. Frustrated, Little B begins to doubt his life choices. Meanwhile, Little A—no stranger to a losing streak—decides to convince Little B to give up the game and focus on studying. He proposes a coin tossing challenge: both toss b coins, and Little A wins if the number of heads he gets is greater than the number of heads Little B gets.

However, having once suffered through his own misadventures in a similar game, Little A is not fully confident in his luck. So, while Little B isn’t looking, Little A secretly cheats by tossing an extra r coins. In other words, Little A tosses a total of b + r coins, while Little B tosses only b coins. Let the number of heads obtained from Little A’s initial b tosses be \(X\), the number of heads from his extra r tosses be \(Y\), and Little B’s number of heads be \(Z\). Then Little A wins if and only if \[ X + Y > Z. \]

Your task is to calculate the total number of possible outcomes (each coin toss having 2 equally likely outcomes) in which Little A wins. Since the answer might be very large, output the last \(k\) digits of the answer. If the result has fewer than \(k\) digits, pad it with leading zeros.

Note: The total number of outcomes is \(2^{(2b+r)}\) because Little A tosses \(b+r\) coins and Little B tosses \(b\) coins.

inputFormat

The input consists of three space‐separated integers:

1. b: the number of coins both players initially toss,
2. r: the number of extra coins tossed by Little A,
3. k: the number of digits to output (i.e. output the last \(k\) digits, padding with leading zeros if necessary).

outputFormat

Output a single string representing the last \(k\) digits of the total number of winning outcomes for Little A.

sample

1 0 2

01