餐馆

小 W 家新开了一家餐馆。

这家餐馆提供 $n$ 种特色菜，它们被标号为 $1,2,\cdots,n$。 有一天，餐馆里来了 $k$ 个客人，他们没有想好要吃什么。于是，小 W 给他们出了个主意：每个人先从 $1,2,\cdots,n$ 中等概率随机一个数 $r$，再从 $1,2,\cdots,r$ 中等概率随机一个数 $l$，这个人就点标号在 $l$ 和 $r$ 之间（包括 $l$ 和 $r$）的菜。 于是，客人们按小 W 说的做了。在所有客人都点完单之后，小 W 突然发现：没有两个人都点了相同的一道菜，他每种菜至多做一份就够了！为了证明他是多么的欧皇，他找到了学编程的你，请你帮他计算这种情况发生的概率。

两个整数 $n$ 和 $k$，意义如题目描述。

一个整数 $p$，表示所求概率对 $10^9+7$ 取模后的结果。

10 1

1

2 2

250000002

样例解释： 样例 $1$ 解释：因为只有一位客人，所以无论如何不会有两个人点同样的菜，故所求概率为 $1$。 样例 $2$ 解释：每位客人只点 $1$ 号菜的概率为 $\dfrac12$，只点 $2$ 号菜的概率为 $\dfrac14$，两个菜都点的概率为 $\dfrac14$，两人不点同一道菜即一人只点 $1$ 号菜，一人只点 $2$ 号菜，概率为 $\dfrac14\times\dfrac12+\dfrac12\times\dfrac14=\dfrac14$，模 $10^9+7$ 意义下为 $250000002$。 ********* 提示：如果你不知道如何对有理数取余，请看 [P2613](https://www.luogu.com.cn/problem/P2613)。 ******** 数据范围： 对于 $10\%$ 的数据， $k=1$。 对于另外 $10\%$ 的数据， $1\le k\le n\le5$。 对于另外 $20\%$ 的数据， $1\le k\le3$。 对于另外 $30\%$ 的数据， $1\le k\le n\le10^3$。 对于所有数据， $1\le k\le n\le 10^8$。