题目描述

你进入了一个闯关游戏，在进入这个游戏的时候，你持有$\red{n}$个魔法球，每一个魔法球都有一个在区间$\red{[0,1]}$之内随机的魔力值。你一共需要通过$\red{m}$道关卡，在通过每一道关卡的时候，你有$\red{\frac{1}{2}}$的概率会消耗掉魔力值最大的魔法球，也有$\red{\frac{1}{2}}$的概率会消耗掉魔力值最小的魔法球。

那么你能否计算出通关后剩余的魔力值期望之和呢？答案对$\red{10^9+7}$取模。

输入格式

第一行输入一个整数$\red{T}$表示输入的组数；

后面$\red{T}$行每一行包含两个整数$\red{n,m}$表示魔法球的个数和关卡数。

输出格式

输出$\red{T}$行，每行一个整数表示答案

样例

输入样例

2
2 2
3 1

输出样例

0
1

提示

对于$\red{100\%}$的数据，$\red{1<=T<=10^5,1<=m<=n<=10^9}$