1555: 上锁的抽屉

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：8 Solved：5

Description

有一只很大的抽屉柜，柜子里竖排了 n 只抽屉。每只抽屉有一把锁。注意，如果只把某一只抽屉锁上，并不意味着这层抽屉就被锁死了——因为它的上层抽屉可能是可以抽出的。
要把一只抽屉锁死，就必须锁上它自己，而且要把它的上一层抽屉也锁上。此外，由于最上层抽屉没有更上层，所以要锁死最上层抽屉只需要锁上自己即可。
请问有多少种上锁的方法，可以恰好锁死 m 只抽屉？由于答案可能很大，输出方案数模 1,000,000,007 的余数。

Input

两个整数：表示 n 与 m。

Output

单个整数：表示答案模 1,000,000,007的余数。

Sample Input Copy 

4 2

Sample Output Copy 

4

HINT

对于 30% 的数据，1≤m≤n≤20；
对于 60% 的数据，1≤m≤n≤300；
对于 100% 的数据，1≤m≤n≤5000。

样例说明：
第一种方法是锁上最高的两层
第二种方法是锁上最高的一层与最低的两层
第三种方法是锁上最高的两层与最低的一层
第四种方法是锁上最低的三层

Source/Category

SubmitSubmit RecordStatisticsShowOff!