#P3079. 方案计数

    ID: 2212 传统题 1000ms 512MiB 尝试: 34 已通过: 21 难度: 8 上传者: 标签>CF2500提高+/省选-普通生成函数单位根筛二项式定理欧拉函数筛法计算积性函数组合数乘法递推逆元线性递推模逆元快速幂

方案计数

题目描述

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

输入格式

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

输出格式

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

7 4
5

数据规模与约定

对于 100%100\% 的数据,1≤n≤1091\le n\le 10^9,1≤k≤1031\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\}$。