SP27375 VECTAR12 - Garden of Mangu

Mangu 为自己购买了一个新花园。这个花园在两个方向上是无限的，即可以无限往 +x 方向和 +y 方向扩展。花园中的方格编号如图所示。Changu 来拜访 Mangu，看到了他的花园。他最开始站在 (0,0) 这个位置。Changu 可以根据需要从一个方格移动到周围的 8 个方向中的任意一个。任务是在 n 步内从 (0,0) 移动到目标位置 (n,k)。你的任务是计算从起点到目标位置共有多少条可能的路径。

第一行输入一个整数 $T$，表示测试用例的数量。接下来是 $T$ 行，每行包含两个整数 $n$ 和 $k$，用空格分隔。

对于每个测试用例，输出可能路径数量对 $1000000007$ 取模的结果。

- $1 \le T \le 10^5$ - $1 \le n \le 10^5$ - $-n \le k \le n$ **本翻译由 AI 自动生成**