说明

有多少个长度为 $n$ 的正整数数列 $a_i$ 满足：

• $0<a_1\leq a_2\leq a_3\dots \leq a_n\leq k$。
• $\forall i\not = j,a_i+a_j\not = k+1$。

答案对 $10^9+7$ 取模。

输入格式

本题多测

第一行一个正整数表示 $T$。

接下来 $T$ 行，每行两个正整数表示 $n,k$。

输出格式

$T$ 行，每行一个正整数表示答案。

3
2 2
1145 1419
19198 12321

2
66937457
949924930

提示

本题采用捆绑测试

• $\text{subtask1(20pts)}:T=5,1\leq n,k\le5$。
• $\text{subtask2(80pts)}:$ 无特殊限制。

对于 $100\%$ 的数据，$T\leq100,1\le n,k\le 5\times 10^6,1\leq \sum n, \sum k\le6\times 10^7$。