题目描述

有一栋有 $n$ 个房间的建筑，编号从 1 到 $n$。

我们可以从建筑中的任意一个房间移动到任意另一个房间。

我们称以下事件为一次移动:一个人从某个房间$i$前往另一个房间 $j(i ≠ j)$。

最初，建筑中的每个房间都有一个人。

然后，我们知道到目前为止一共发生了$k$次移动。 我们对现在每个房间中的人数感兴趣。有多少种可能的房间人数组合?

将计数对$(10^9+ 7)$取模。

输入

第一行输入两个整数$n,k$

输出

打印可能的房间人数组合数，对$10^9+7$取模。

3 2

10

样例解释

设$c_1,c_2,c_3$是示当前房间1、2 和 3 中的人数。有 10种可能的组合 - $(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)$ 例如，如果房间1中的人前往房间 2，然后房间2中的其中一个人前往房间 3，则$(c_1,c_2,c_3)$将是$(0,1,2)$。

200000 1000000000

607923868

15 6

22583772

提示

• $3\ \leq\ n\ \leq\ 2\ \times\ 10^5$
• $2\ \leq\ k\ \leq\ 10^9$