QOJ.ac

QOJ

Time Limit: 8 s Memory Limit: 256 MB Total points: 100

# 8702. 狼人杀

统计

狼人杀是一款经久不衰的身份推理类桌游。在一局狼人杀的游戏中,每名玩家都会被分配到"村民"、"狼人"、"预言家"等身份。狼人需要尽可能地隐藏自己,预言家可以在晚上查验玩家的身份,而村民则要在预言家的带领下找出狼人。

今天,九条可怜和她的小伙伴们开了一局 $n$ 名玩家参与的游戏。在这局游戏中,玩家从 $1$ 到 $n$ 编号,而可怜的编号是 $m$。

与传统狼人杀不同的是,这局游戏中的身份包含一名狼人,一名预言家,和 $n-2$ 名村民。每个晚上,只有预言家能够行动(即狼人并不能刀人):扮演预言家的玩家需要选择一个玩家编号的区间 $[l, r]$,而他/她会得知狼人的编号是否在这个区间中。

可怜分配到的身份是狼人,于是她想要估算一下自己隐藏身份的难度。假设可怜的每名小伙伴都有相同的概率扮演预言家(每名小伙伴 $\frac{1}{n-1}$ 的概率),且每个晚上预言家从所有区间中等概率地选择查验区间(每个区间 $\frac{2}{n(n+1)}$ 的概率)。可怜想要知道期望在多少个夜晚后,预言家得到的信息能够唯一确定可怜就是那名狼人。

Input

输入包含一行两个整数 $n,m (2 \leq n \leq 150, 1 \leq m \leq n)$,表示玩家的总数和可怜的编号。

注意:本题的代码长度限制为 8kB。

Output

输出一行一个整数,表示答案对 $1,000,000,007$ 取模后的值,换句话说,如果答案的最简分数表示为 $x/y$,那么你需要输出 $x \times y^{1,000,000,005} \text{ 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$。所以,答案就是 $\sum_{i=1}^{+\infty} (1/2)^i \cdot 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 \leq n \leq 20$。

子任务二($34$ 分),$1 \leq n \leq 50$。

子任务三($43$ 分),$1 \leq n \leq 150$。

注意:本题的代码长度限制为 8kB。