8704: Problem G. 交作业

内存限制:256 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:12 通过:2

题目描述

“叮叮叮”,上课了,小E准备从书包里拿出作业交作业,但他发现他书包里的作业本太多了,他不知道昨天写的作业在哪里,他只好从书包中随机拿一本出来。小E的书包有很多作业,其中只有一本是现在要交的作业,如果拿出来的不是要交的作业,小E有两种选择,要么将作业放回书包里,要么将作业拿放在桌子上,然后继续往书包拿。因为桌子不是无限大的,桌子只能放一定数量的作业,之后只能将作业放回书包。请你告诉小E他拿到正确作业本的最少期望次数。

为了避免精度问题,请将结果对 $10^9+7$ 取模。即,我们的数据保证答案是一个有理数 $\frac{p}{q}$,且有 $10^9+7\nmid q$,你只需要找到一个整数 $x\in [0, 10^9+7)$ 使得 $qx\equiv p\pmod{10^9+7}$ 即可。


输入格式

输入只有一行,包含两个整数,分别为$n$和 $m$,代表作业本数和桌子的容量。$(1\le n \le 10^6,0 \le m \le n)$

输出格式

输出一个整数,值为 $p\cdot q^{-1}\mod{10^9+7} $

输入样例 复制

2 1

输出样例 复制

500000005

数据范围与提示

样例输入2:

2 0

样例输出2:

2



对于第一个样例:

第一次拿到正确作业本的概率为$\frac{1}{2}$;否则小E可以将这本作业本放到桌子上,第二次一定能拿到正确的作业本,概率为$\frac{1}{2}\cdot1$,期望为$\frac{1}{2}\cdot1+\frac{1}{2}\cdot2=\frac{3}{2}$

对于第二个样例:

小E不能将作业本放到桌子上,每次拿错了只能返回书包里,那么第一次拿到正确作业本的概率为$\frac{1}{2}$,第二次拿到正确作业本的概率为$\frac{1}{2}\cdot\frac{1}{2}$,第三次拿到正确作业本的概率为$\frac{1}{2}\cdot\frac{1}{2}\cdot\frac{1}{2}$,以此类推,那么期望为$\sum\limits_{i=1}^{\infty}(\frac{1}{2})^i\cdot i = 2$