抢红包

出题

---

gzp 最近由于找工作刷 leetcode 加入了一个“残酷刷题群”，群规真的非常残酷，14 条群规有 9 条都需要发红包，严格执行的群规导致新人的高淘汰率，高淘汰率同时决定群内留下的都是高质量“刷题家”，其中不乏三四名 leetcode rating 全国排名前 10 或者 cf 红名大神。

每次周赛结束后就是群里的红包高峰期，现假设一个拼手气红包内总共有 $m$ 分（红包金额的最小单位：分），群里有 $n$ 人抢红包，第 $i~(i\neq n)$ 个人打开红包时，若此时红包还剩下 $x$ 分，他可以等概率地抢到在 $[1,x-(n-i)]$ 区间内的红包金额，即最少 $1$ 分红包，最多也要给还没抢到红包的 $n-i$ 人每人留 $1$ 分，第 $n$ 个人将得到剩下所有红包，问最后一个人抢到红包的期望值。

注：

• 请忽略实际拼手气红包的分配规则，以题面描述规则计算期望；
• 期望的计算规则：设第 $n$ 个人有 $p_1$ 的概率得到 $x_1$ 分，有 $p_2$ 的概率得到 $x_2$ 分……有 $p_k$ 的概率得到 $x_k$ 分，则他获得红包的期望值为：$\sum_{i=1}^kp_ix_i$。

输入

输入包含两个整数 $n,m$，分别表示抢红包的人数与红包金额（单位：分）。

输出

若最后一个人抢到红包的期望值用分数表示为 $E=\frac{p}{q}$，则输出一个整数 $E'$ 满足 $E'\times q\equiv p\mod10^9+7$（或者说 $E'\times q~\%~(10^9+7)=p~\%~(10^9+7)$）。

样例输入

2 6

样例输出

3

样例解释

第二个人得到红包的金额概率分布为：

金额（单位：分）	1	2	3	4	5
概率	$\frac{1}{5}$	$\frac{1}{5}$	$\frac{1}{5}$	$\frac{1}{5}$	$\frac{1}{5}$

因此获得的红包金额期望为：

$$E=1\times\frac{1}{5}+2\times\frac{1}{5}+3\times\frac{1}{5}+4\times\frac{1}{5}+5\times\frac{1}{5}=3$$

数据范围

对于 $10\%$ 的数据，$1\leq n\leq2,~2\leq m\leq100$；

对于 $60\%$ 的数据，$1\leq n\leq m\leq100$；

对于 $100\%$ 的数据，$1\leq n\leq m\leq5000$。

题解

出门右转就能看见。