狼人杀是一款经久不衰的身份推理类桌游。在一局狼人杀的游戏中,每名玩家都会被分配到"村民"、"狼人"、"预言家"等身份。狼人需要尽可能地隐藏自己,预言家可以在晚上查验玩家的身份,而村民则要在预言家的带领下找出狼人。
今天,九条可怜和她的小伙伴们开了一局 n 名玩家参与的游戏。在这局游戏中,玩家从 1 到 n 编号,而可怜的编号是 m。
与传统狼人杀不同的是,这局游戏中的身份包含一名狼人,一名预言家,和 n−2 名村民。每个晚上,只有预言家能够行动(即狼人并不能刀人):扮演预言家的玩家需要选择一个玩家编号的区间 [l,r],而他/她会得知狼人的编号是否在这个区间中。
可怜分配到的身份是狼人,于是她想要估算一下自己隐藏身份的难度。假设可怜的每名小伙伴都有相同的概率扮演预言家(每名小伙伴 1n−1 的概率),且每个晚上预言家从所有区间中等概率地选择查验区间(每个区间 2n(n+1) 的概率)。可怜想要知道期望在多少个夜晚后,预言家得到的信息能够唯一确定可怜就是那名狼人。
Input
输入包含一行两个整数 n,m(2≤n≤150,1≤m≤n),表示玩家的总数和可怜的编号。
注意:本题的代码长度限制为 8kB。
Output
输出一行一个整数,表示答案对 1,000,000,007 取模后的值,换句话说,如果答案的最简分数表示为 x/y,那么你需要输出 x×y1,000,000,005 mod 1,000,000,007 的值。
Examples
Input 1
2 2
Output 1
0
Input 2
3 2
Output 2
2
Input 3
3 3
Output 3
750000007
Input 4
10 5
Output 4
470594541
Notes
在第一组数据中,只有两名玩家,因此预言家不需要发动技能就能知道另一名玩家(即可怜)是狼人。
在第二组数据中,不妨假设预言家的编号是1(另一种情况对称),那么只有当预言家问出 [1,2],[2,2] 或者 [3,3] 时,才能唯一确定狼人身份。因此预言家在第 i 个夜晚后才能首次确定可怜身份的概率是 (1/2)i。所以,答案就是 ∑+∞i=1(1/2)i⋅i=2。
在第三组数据中,根据预言家编号的不同有着两种情况。
- 如果预言家的编号是 1,那么只有当预言家问出 [1,2],[2,2] 或 [3,3] 时才能唯一确定狼人身份,此时期望需要的夜晚数为 2。
- 如果预言家的编号是 2,那么只有当预言家问出 [1,1],[1,2],[2,3] 或 [3,3] 时才能唯一确定狼人身份,此时期望需要的夜晚数量为 3/2。
综合两种情况,答案就是 (2+(3/2))/2=7/4。
Scoring
子任务一(23 分),1≤n≤20。
子任务二(34 分),1≤n≤50。
子任务三(43 分),1≤n≤150。
注意:本题的代码长度限制为 8kB。