bzoj#P3079. 方案计数

方案计数

题目描述

{0,,n1}\{0,\cdots,n-1\}nn 个数字中选 kk 个数字总共有多少种方案?显然有 n!k!×(nk)!\frac{n!}{k!\times(n-k)!} 种方案。在这些方案中,有多少种方案,它们的数字和(不是数位和)能被 nn 整除?

输入格式

第一行包括两个整数 n,kn,k

输出格式

一个整数,为方案数 mod(109+7)\bmod(10^9+7) 后的值。

7 4
5

数据规模与约定

对于 100%100\% 的数据,1n1091\le n\le 10^91k1031\le k\le 10^3

提示

总共是以下 55 种方案: $\{0,1,2,4\},\{0,3,5,6\},\{1,2,5,6\},\{1,3,4,6\},\{2,3,4,5\}$。