题目描述

给出三个正整数 $N,M,K$，求 $C_{N+M}^N$ 去掉所有末尾的 $0$ 后对$10^K$ 取模的结果。

输入格式

一行三个整数 $N \ M \ K \ (1 \le N,M \le 10^{15},1 \le K \le 18)$ 。

输出格式

一行一个整数（可能有前导零）。

样例输入

11 5 9

样例输出

000004368