[Ontak2013]Kapita加强版

时间限制:2s    【提交】    空间限制:128MB

题目描述

  同3738,即给出三个数字N,M,K,求C(N+M,N)去掉所有末尾的0后对10^k取模的结果。


输入格式


输出格式


样例输入

11 5 9

样例输出

000004368

提示

1<=N,M<=10^15,1<=k<=18


题目来源

By Tangjz