牛能来到了 "小荷山"，他发现这里的山脉海拔与坐标存在一个规律。
考虑山脉的每一座山的坐标在一条直线上，我们用数轴来表示山脉的坐标。
这些山脉的海拔大小都在一个范围之内，我们定义海拔最高的山为 "尖" 。
这个特殊的规律可以表示为：对于 “尖” 的左侧山脉，从左到右山脉的海拔大小呈不下降；
对于 “尖” 的右侧山脉，从右到左山脉的海拔大小呈不下降。而对于所有满足此规律的山脉定义为 "神奇风景"。
由于牛牛并未能够来到这片神奇的山脉，他希望知道 "小荷山" 山脉的神奇风景。
然而牛能并不希望牛牛直接领略到 “小荷山” 的神奇风景，他希望在牛牛求出 “小荷山” 有多少种不同的神奇风景后，再告诉牛牛具体的神奇风景。
然而牛牛算不出来，但是他迫切的希望能够领略到 “小荷山” 的神奇风景，于是他将这个任务交由精通 OI 和 "组合数学" 的你来完成。
我们定义两种神奇风景不同，当且仅当存在某一坐标处的山脉海拔大小不同。
形式化地说，现在从[1,n]中选出m个数生成一个序列，求生成序列恰好为 "单峰序列" 的方案数。
我们定义两个序列不相同，当且仅当存在某一相同位置所放置的数不同。
要求解决t组数据。
要求答案对1e9 + 7取模。
输入描述:
共 t+1行 .
第1行，仅1个数 , t.
第2行至第t+1行，每行2个数： n，m .
输出描述:
共 t 行 .
第1行至第 t 行，每行1个数表示方案数对1e9 + 7取模后的结果
示例1
说明
当 n = 2,m = 3 时，符合条件的序列有 {1,1,1},{1,1,2},{1,2,1},{1,2,2},{2,1,1},{2,2,1},{2,2,2}，不符合条件的序列有 {2,1,2}，故答案为 7 .
示例2
输入
复制
4
26 26
262 626
62626 26262
2626262 2626266
输出
复制
318836234
471802003
756001620
760321595
备注:
对于 5% 的数据，我们约定：1 ≤ t ≤ 10,1 ≤ n ≤ 6,1 ≤ m ≤ 6
对于另外 5% 的数据，我们约定：1 ≤ t ≤ 10,1 ≤ n ≤ 5e5 ,m = 2
对于另外 10% 的数据，我们约定：1 ≤ t ≤ 10,1 ≤ n ≤ 5e5 ,3 ≤ m ≤ 5
对于另外 20% 的数据，我们约定：1 ≤ t ≤ 10,1 ≤ n ≤ 200 ,1 ≤ m ≤ 200
对于另外 10% 的数据，我们约定：1 ≤ t ≤ 10,1 ≤ n ≤ 1e3 ,1 ≤ m ≤ 1e3
对于另外 30% 的数据，我们约定：1 ≤ t ≤ 10,1 ≤ n ≤ 1e5 ,1 ≤ m ≤ 1e5
对于 100% 的数据，我们约定：1 ≤ t ≤ 10,1 ≤ n ≤ 5e6 ,1 ≤ m ≤ 5e6