给出M,N,K，求C(M,N)的十进制表示的最后K位。例如M = 18, N = 8, K = 3，C(18,8) = 18!/8!/10! = 43758，最后3位数是758。

输入

第1行：M。（2 <= M <= 10^100)。

第2行：N。（2 <= N <= M)。

第3行：K。（1 <= K <= 100)。

输出

输出结果的后K位。

输入样例 18

8

3

输出样例

758

#include<iostream>
using namespace std;
int CK(int n)
{
	if(n == 0||n == 1)return 1;
	else return n * CK(n-1);
}
int Cre(int n, int m){
	return (CK(n) / CK(n-m) / CK(m));
}
int main()
{
	int n,m;
	cin>>n>>m;
	cout<<Cre(n, m);
	return 0;
}