题目描述

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

输出方案数对 $10^9+7$ 取模。

输入格式

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

输出格式

一行一个整数表示答案。

7 4

5

数据规模与约定

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