#P18489. Cola
Cola
Cola
Alice 有一个喜欢的排列 ,它是 的一个排列。Bob 得知,如果他猜中了 ,Alice 就会送他一瓶可乐。于是 Bob 决定通过向 Alice 提问来猜出 。
Bob 最多可以提问 次,每次问题如下:选择一个 的排列 ,询问 Alice 她喜欢的排列是否就是 。其中 。
Alice 的回应规则为:
- 如果 ,Alice 送给 Bob 一瓶可乐。
- 如果 ,Alice 告诉 Bob 满足 的最小下标 。
例如,如果 ,Bob 提问的排列为 ,Alice 会告诉他:存在不相等的位置,最小下标为 。
即使 Bob 在第 次提问之后已经能够确定 ,只要这些提问中没有实际猜中,他也不会获得可乐。
最初 Bob 对 没有任何信息。请计算他获得可乐的最大概率,并输出这个概率模 的值。
这是一个离线计算题:输入只有 ,程序只输出一个概率值,不进行上述提问交互。
概率模 的定义
可以证明,所求概率总是有理数。在本题约束下,将概率写成最简分数 后,保证分母 不被 整除。此时,存在唯一整数 满足 且
输出这个 。
输入格式
N M
输入中的数均为整数,满足 。本题没有测试用例数量 。
输出格式
输出所求的概率模 的值。
样例 1
输入:
2 1
输出:
499122177
只能提问一次,可能的排列有两个,所以得到可乐的最大概率为 。即使第一次猜错后已经能确定排列,也不能因此获得可乐。
样例 2
输入:
1 1
输出:
1
Bob 在第一次提问时一定能获得可乐。
样例 3
输入:
167 91
输出:
469117530