小 C 有一份 $n$ 道题的作业。每道题仅有 A/B 两个选项。

但是小 C 很笨，所以他只会依次按 ABABAB.... 填写答案。填对的题就完成了，填错的答案会按原顺序进入错题重练本。小 C 会继续用上述方法填写剩下的题目，直到所有题都完成。

小 C 不想花太多时间写作业，请问对于所有 $2^n$ 种标准答案，需要恰好 $k$ 次作答完成的方案数。

特别的，若 $k=-1$，则你需要求出永远也无法完成的方案数。

现在小 C 有 $T$ 份作业，请你帮他求出答案。由于答案可能特别大，请 $\bmod 10^9+7$ 后输出。

输入格式

第一行一个整数 $T$，表示询问次数。

接下来对于每个询问，一行两个整数 $n,k$，表示题目数量和完成次数。

输出格式

对于每个询问，输出一行一个整数，表示可能的方案数 $\bmod 10^9+7$。

样例输入

5
3 2
5 -1
20 7
1234 5
11451 4

样例输出

2
22
0
347568647
713703651

样例解释

对于第一组询问，可能的答案为 AAA 或 AAB。

数据范围

对于所有数据，满足 $T\le 5,1\le n\le 2\times 10^6,-1\le k\le 2\times 10^6$。