题目描述

Bob 有 $n$ 个盒子，依次编号为 $1 \dots n$, 最开始每个盒子中有 $1$ 个苹果.

操作 1 次定义如下：将第 $i$ 个盒子中的一个苹果，移动到第 $j$ 个盒子中 $(i \ne j)$。

Bob 操作 $k$ 次后，请问 $n$ 个盒子有多少种可能的排列情况？第 $i$ 个盒子中苹果数量不同就算不同的情况。

种类会很多，只需要输出 $10^9+7$ 的余数就可以了。

盒子无限大，可以放下任意多个苹果。

输入格式

两个整数 $n$ $k$

输出格式

一个整数，表示结果

3 2

10

样例1解释

3 个盒子经过 2 次移动后，有如下情况：

$(0,1,2),(0,2,1),(1,0,2),(2,0,1),(2,1,0),(1,2,0),(1,1,1),(0,0,3),(0,3,0),(3,0,0)$

共 10 种情况。其中 $(0,1,2)$ 可以是第一次将第1个盒子中的 1 个苹果移动到第 2 个盒子，第二次将第2个盒子中的 1 个苹果移动到第 3 个盒子中。$（1,1,1）$可以是第一次将第 1 个盒子中的 1 个苹果移动到第 2 个盒子中，第二次将第 2 个盒子中的 1 个苹果移动到第 1 个盒子中。

100 1000

703668401

100000 100000

939733670

数据规模与约定

subtask1: $3 \leq n,k \leq 20$，$40$分

subtask2: $3 \leq n,k \leq 10^4$，$20$分

subtask3: $3 \leq n \leq 2*10^5，2 \leq k \leq 10^9$，$40$分