二分

有 $n$ 个格子，你现在在第 $x$ 个格子，想到第 $y$ 个格子。

每次，如果你当前的格子编号小于 $y$，你就会等概率跳到比当前编号更大的一个格子中，反之则等概率跳到比当前编号更小的一个格子中。

求期望跳的次数。

第一行一个正整数 $T$ 代表数据组数。

接下来 $T$ 行，每行三个正整数 $n,x,y$，分别为函数的三个参数。

满足 $1\le n,T \le 2\times 10^6$，$1\le x,y\le n$。

对每组数据，输出一个正整数，$i$ 的期望对 $10^9+7$ 取模后的值。

4
2 1 2
3 1 3
3 1 2
114514 1919 810

1
500000005
2
680707294

对于第一组 $n=2$，$x=1$，$y=2$ 的情况，第一次跳跃的范围为 $[2,2]$，因此答案为 $1$。

对于第二组 $n=3$，$x=1$，$y=3$ 的情况，第一次跳跃的范围为 $[2,3]$。

若第一次跳到第 $2$ 格，答案为 $2$；若第一次跳到第三格，答案为 $1$，因此答案为 $\frac{1}{2}\times2+\frac{1}{2}\times1\equiv\frac{3}{2}\equiv5\times 10^8+5\pmod{10^9+7}$

对于第三组 $n=3$，$x=1$，$y=2$ 的情况，

有 $\frac{1}{2^n}$ 的情况答案为 $n$，

故答案为 $\sum_{i=1}^{\infin}\frac{i}{2^i}=2$。

2021 年百度之星·程序设计大赛 - 初赛一