有多组数据，对于每组数据输入三个数 $a,b,k$，分别代表小 A 抛硬币的次数，小 B 抛硬币的次数，以及最终答案保留多少位整数。

对于每组数据，输出一个数，表示最终答案的最后 $k$ 位为多少，若不足 $k$ 位以 $0$ 补全。

样例输入

2 1 9
3 2 1

样例输出

000000004
6

样例解释

对于第一组数据，当小 A 抛 $2$ 次硬币，小 B 抛 $1$ 次硬币时，共有 $4$ 种方案使得小 A 正面朝上的次数比小 B 多。

对于第二组数据，当小 A 抛 $3$ 次硬币，小 B 抛 $2$ 次硬币时,共有 $16$ 种方案使得小 A 正面朝上的次数比小B多。

对于 $10\%$ 的数据，$a,b\le 20$；
对于 $30\%$ 的数据，$a,b\le 100$；
对于 $70\%$ 的数据，$a,b\le 100000$，其中有 $20\%$ 的数据满足 $a=b$；
对于 $100\%$ 的数据，1≤a,b≤1015,b≤a≤b+10000,1≤k≤91\le a,b\le {10}^{15}, b\le a\le b+10000, 1\le k\le 91≤a,b≤10​15​​,b≤a≤b+10000,1≤k≤9，数据组数小于等于 $10$。