Problem Description

$N$ numbers, randomly generated between $ [0,1] $

Make $M$ operation, $\frac {1} {2} $ probability to delete the maximum value, $ \frac {1} {2} $ probability to delete the minimum value

Calculate the sum of expected value module $10^9+7 $

Input

Each test contains multiple test cases. The first line contains the number of test cases $T$($1\le T \le 10000$). Description of the test cases follows.

The first line of each test case contains two integers $n,m$

$1\le m \le n \le 10^9$

Output

For each test case, print one integer — the answer to the problem.

2
2 2
3 1

0
1