#P4314. 倍数?倍数!

    ID: 3530 传统题 1000ms 512MiB 尝试: 184 已通过: 100 难度: 8 上传者: 标签>CF2500提高+/省选-普通生成函数单位根筛二项式定理欧拉函数阶乘逆元预处理模逆元快速幂

倍数?倍数!

题目描述

求在 [0,n)[0,n) 中选出 kk 个互不相同的数,使得这些数的和  mod  n\bmod \, n 等于 00 的方案数。

输出方案数对 109+710^9+7 取模。

输入格式

一行两个整数 n,kn,k。

输出格式

一行一个整数表示答案。

7 4
5

数据规模与约定

对于 100%100\% 的数据,1≤n≤1091\leq n\leq 10^9,0≤k≤1030\leq k\leq 10^3。