狼人杀 - 题目

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

今天，九条可怜和她的小伙伴们开了一局 $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

Input 2

3 2

Output 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$。