#11. 球袋
球袋
问题描述
袋子里面有 个红球和 个蓝球,小红和小蓝闭着眼睛轮流从袋子里取球,谁先取出红球谁就获胜。由于小蓝比较马虎,他每次取一个球都一定会导致袋子里面另一个球掉出。同时,如果最后袋子里面球被取完了,且没有人取到红球,则小蓝获胜。
现在给定你 ,你需要求出小红获胜的概率,为了防止精度问题,你需要对 取模。
令 ,可以证明所求概率可以写成既约分数 的形式,其中 均为整数且 。输出的整数应当是 。
输入格式
输入一行,包含 个正整数 。
输出格式
输出小红获胜的概率,对 取模。
样例输入
1 3
样例输出
499122177
说明
有 个红球和 个蓝球,分别有如下情况:
- 小红先手取红球,小红获胜。
- 小红先手取蓝球,小蓝后手取红球,小蓝获胜。
- 小红先手取蓝球,小蓝后手取蓝球,最后一个蓝球掉落,小红获胜。
- 小红先手取蓝球,小蓝后手取蓝球,红球掉落,小蓝获胜。
最终概率是 ,对 取模结果为 。
评测数据规模
。