1265: #2023. 「HNOI2017」抛硬币

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

小 A 和小 B 是一对好朋友,他们经常一起愉快的玩耍。最近小 B 沉迷于**师手游,天天刷本,根本无心搞学习。但是已经入坑了几个月,却一次都没有抽到 SSR,让他非常怀疑人生。

勤勉的小 A 为了劝说小 B 早日脱坑,认真学习,决定以抛硬币的形式让小 B 明白他是一个彻彻底底的非洲人,从而对这个游戏绝望。两个人同时抛 bbb 次硬币,如果小 A 的正面朝上的次数大于小 B 正面朝上的次数,则小 A 获胜。

但事实上,小 A 也曾经沉迷过拉拉游戏,而且他一次 UR 也没有抽到过,所以他对于自己的运气也没有太大把握。所以他决定在小 B 没注意的时候作弊,悄悄地多抛几次硬币,当然,为了不让小 B 怀疑,他不会抛太多次。现在小 A 想问你,在多少种可能的情况下,他能够胜过小 B 呢?由于答案可能太大,所以你只需要输出答案在十进制表示下的最后 kkk 位即可。

输入格式

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

输出格式

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

样例

样例输入

2 1 9
3 2 1

样例输出

000000004
6

样例解释

对于第一组数据,当小 A 抛 222 次硬币,小 B 抛 111 次硬币时,共有 444 种方案使得小 A 正面朝上的次数比小 B 多。

(01,0),(10,0),(11,0),(11,1) (01,0), (10,0), (11,0), (11,1) (01,0),(10,0),(11,0),(11,1)

对于第二组数据,当小 A 抛 333 次硬币,小 B 抛 222 次硬币时,共有 161616 种方案使得小 A 正面朝上的次数比小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) \begin{aligned} (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) \end{aligned} (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)

数据范围与提示

对于 10%10\%10% 的数据,a,b≤20a,b\le 20a,b20
对于 30%30\%30% 的数据,a,b≤100a,b\le 100a,b100
对于 70%70\%70% 的数据,a,b≤100000a,b\le 100000a,b100000,其中有 20%20\%20% 的数据满足 a=ba=ba=b
对于 100%100\%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 91a,b1015,bab+10000,1k9,数据组数小于等于 101010