方案计数

时间限制:10s      空间限制:128MB

题目描述

从{0,…,N-1}这N个数字中选K个数字总共有多少种方案?,显然有N!/K!/(N-K)!种方案。在这N!/K!/(N-K)!种方案有多少种方案,它们的数字和(不是数位和)能被N整除? 
 


输入格式

      第一行包括两个整数N,K
 


输出格式

      一个整数,为方案数mod 1000000007(质数)后的值
 


样例输入

7 4
 

样例输出

5

提示

总共是以下5种方案:
{0,1,2,4}{0,3,5,6}{1,2,5,6}{1,3,4,6}{2,3,4,5}
 
100%的数据满足1<=N<=10^9,1<=K<=1000


题目来源

没有写明来源