题目描述

从 $n$ 个不同元素中，任取 $m(m \le n)$ 个元素并成一组，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个组合；从 $n$ 个不同元素中取出 $m(m \le n)$ 个元素的所有组合的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的组合数，计做 $C_n^m$ .

组合数计算方法如下：

$$C_n^m=\frac{A_n^m}{A_m^m}=\frac{n!}{(n-m)!\cdot m!} $$

（其中 $A_n^m$ 是从 $n$ 个不同元素中，任取 $m(m \le n)$ 个元素构成的排列数。）

组合数具有很多很多性质：

• 1.互补性质： $C_n^m=C_n^{n-m}$

• 2.递推性质: $C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}$

给定 $n$ 和 $m$ ，求 $C_n^m$ 取 $10^9+7$ 的余数。

输入格式

两个整数 $n$ $m$.

输出格式

一个整数，表示 $C_n^m$ 取 $10^9+7$ 的余数.

10 5

数据规模与约定

$subtask1$ : $1 \le m\le n \le 10$ , $10$ 分 （直接算）

$subtask2$ : $1 \le m\le n \le 10^3$ , $20$ 分 （递推，杨辉三角）

$subtask3$ : $1 \le m\le n \le 10^4$ , $20$ 分 （递推，空间优化）

$subtask4$ : $1 \le m\le n \le 2 \times 10^5$ , $50$ 分 （逆元）