Migrated from Lutece 3229 米奇妙妙程序

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

初始一个长为 $n$ 的序列 $\{a_n\}$，下标从 $1$ 开始，所有元素均为 $0$。且有变量 $Fail$，初值为 $0$。

现执行以下操作 $m$ 次：

1. 从 $\{1,2,\dots,n\}$ 中等概率选取一个值，记为 $p$。
2. 若 $a_p=0$ ，则置 $a_p$ 为 1，否则：
   1. 从 $\{0,1\}$ 中等概率选取一个值，记为 $x$。
   2. 若 $x=0$ ，则找到最小的 $i$，满足 $a_i=0$ 且 $i>p$； 若 $x=1$ ，则找到最大的 $i$，满足 $a_i=0$ 且 $i<p$。
   3. 若 $i$ 存在，置 $a_i=1$； 否则，置 $Fail=1$ 。

求 $P(Fail=0)$ 在模 $10^9+7$ 意义下的结果。

Input

本题采用多测，第一行，一个正整数 $T$ ，表示数据组数

对于每组数据，一行，两个正整数 $n$ 和 $m$。

Output

对于每组数据，一行，一个整数，表示答案。

Samples

2
2 1
2 2

1
750000006

Constraints

$1\leq m\leq n\leq 10^5$，$1\leq T \leq 10^2$

Resources

2024 UESTC ICPC Training for Math