漫游

（roaming.cpp 2s/1024MB）

题目描述

有$n$不同个房间,每个房间有$1$个人。人可以在各个房间中移动（不能原地移动）。

所有人一共移动了$k$次，问最后各个房间人数排列有多少种情况。

最后方案数对$10^9+7$取模

提示：所有人是相同的，当且仅当存在两个房间的人数不同时可以认为是不同的方案。

输入格式

共一行,两个整数$n,k$.

输出格式

输出方案数对$10^9+7$取模的结果

样例

输入样例1

3 2

输出样例1

10

样例1解释：

所有方案数如下（括号里的数字表示不同房间的人数）：

(0,0,3)，(0,1,2)，(0,2,1)，(0,3,0)，(1,0,2)，(1,1,1)，(1,2,0)，(2,0,1)，(2,1,0)，(3,0,0)共10种

输入样例2

200000 1000000000

输出样例2

607923868

数据范围与提示

$3≤n≤2×10^5$

$2≤k≤10^9$