#P18015. Forgot to Refuel
Forgot to Refuel
Forgot to Refuel
一条可以双向行驶的环路周长为 千米。环路上有 个路口,相邻两个路口沿环路的距离都为 千米。
其中恰有 个不同路口设有加油站,每个路口至多一个加油站。所有满足条件的加油站布局等概率出现。
司机刚刚错过一个加油站入口,不能掉头,只能继续沿原方向行驶。对于一个固定的加油站布局,考虑所有可能的出发位置和行驶方向,到达下一个加油站所需行驶距离的最坏值;它就是相邻加油站沿环路的最大间距。
求这个最大距离在所有加油站布局中的期望,对 取模。
输入格式
一行两个整数 。
输出格式
输出一个整数,表示所求期望对 取模的结果。
若期望的最简分数是 ,则输出 。题目保证 不被该模数整除。
数据范围
。
说明
当 时,有五种布局的三个间距为 ,另五种为 ,所以所求期望为 。
样例 1
输入
2 2
输出
1
样例 2
输入
5 3
输出
499122179
样例 3
输入
20 5
输出
796329095