题目描述

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

输入格式

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

输出格式

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

7 4

5

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 10^9$，$1\le k\le 10^3$。

提示

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