CF1498C.Planar Reflections

Gaurang has grown up in a mystical universe. He is faced by $n$ consecutive 2D planes. He shoots a particle of decay age $k$ at the planes.

A particle can pass through a plane directly, however, every plane produces an identical copy of the particle going in the opposite direction with a decay age $k-1$. If a particle has decay age equal to $1$, it will NOT produce a copy.

For example, if there are two planes and a particle is shot with decay age $3$ (towards the right), the process is as follows: (here, $D(x)$ refers to a single particle with decay age $x$)

1. the first plane produces a $D(2)$ to the left and lets $D(3)$ continue on to the right;
2. the second plane produces a $D(2)$ to the left and lets $D(3)$ continue on to the right;
3. the first plane lets $D(2)$ continue on to the left and produces a $D(1)$ to the right;
4. the second plane lets $D(1)$ continue on to the right ($D(1)$ cannot produce any copies).

In total, the final multiset $S$ of particles is ${D(3), D(2), D(2), D(1)}$. (See notes for visual explanation of this test case.)

Gaurang is unable to cope up with the complexity of this situation when the number of planes is too large. Help Gaurang find the size of the multiset $S$, given $n$ and $k$.

Since the size of the multiset can be very large, you have to output it modulo $10^9+7$.

Note: Particles can go back and forth between the planes without colliding with each other.

高兰在一片神秘宇宙中长大。他面对着 $n$ 个连续排列的二维平面，并向这些平面发射一个衰变寿命为 $k$ 的粒子。

一个粒子可以直接穿过某个平面；但每当它穿过一个平面时，该平面会生成一个完全相同的粒子，以相反方向运动，且其衰变寿命为 $k-1$。若粒子的衰变寿命等于 $1$，则它不会产生任何副本。

例如，假设有两个平面，且一个衰变寿命为 $3$ 的粒子（向右发射）射向它们，则整个过程如下（此处 $D(x)$ 表示一个衰变寿命为 $x$ 的粒子）：

1. 第一个平面向左产生一个 $D(2)$，同时允许 $D(3)$ 继续向右前进；
2. 第二个平面向左产生一个 $D(2)$，同时允许 $D(3)$ 继续向右前进；
3. 第一个平面允许向左运动的 $D(2)$ 继续向左前进，并向右产生一个 $D(1)$；
4. 第二个平面允许向右运动的 $D(1)$ 继续向右前进（$D(1)$ 无法产生任何副本）。

最终得到的粒子多重集 $S$ 为 $\{D(3), D(2), D(2), D(1)\}$。（参见注释中对该测试用例的图示解释。）

当平面数量过大时，高兰无法应对这一情形的复杂性。请帮助高兰求出多重集 $S$ 的大小（即其中粒子总数），给定 $n$ 和 $k$。

由于多重集大小可能非常大，请将结果对 $10^9+7$ 取模后输出。

注：粒子可在各平面之间来回运动，且彼此之间不会发生碰撞。

The first line of the input contains the number of test cases $t$ ($1 \le t \le 100$). Then, $t$ lines follow, each containing two integers $n$ and $k$ ($1 \le n, k \le 1000$).

Additionally, the sum of $n$ over all test cases will not exceed $1000$, and the sum of $k$ over all test cases will not exceed $1000$. All test cases in one test are different.

输入的第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是 $t$ 行，每行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 1000$）。

此外，所有测试用例中 $n$ 的总和不超过 $1000$，所有测试用例中 $k$ 的总和也不超过 $1000$。同一组测试中的所有测试用例互不相同。

Output $t$ integers. The $i$-th of them should be equal to the answer to the $i$-th test case.

输出 $t$ 个整数。其中第 $i$ 个整数应等于第 $i$ 个测试用例的答案。

Let us explain the first example with four test cases.

Test case 1: ($n = 2$, $k = 3$) is already explained in the problem statement.

See the below figure of this simulation. Each straight line with a different color represents the path of a different particle. As you can see, there are four distinct particles in the multiset. Note that the vertical spacing between reflected particles is for visual clarity only (as mentioned before, no two distinct particles collide with each other)

Test case 2: ($n = 2$, $k = 2$) is explained as follows:

1. the first plane produces a $D(1)$ to the left and lets $D(2)$ continue on to the right;
2. the second plane produces a $D(1)$ to the left and lets $D(2)$ continue on to the right;
3. the first plane lets $D(1)$ continue on to the left ($D(1)$ cannot produce any copies).

Total size of multiset obtained ${D(1), D(1), D(2)}$ is equal to three.

Test case 3: ($n = 3$, $k = 1$), there are three planes, but decay age is only one. So no new copies are produced while the one particle passes through the planes. Hence, the answer is one.

Test case 4: ($n = 1$, $k = 3$) there is only one plane. The particle produces a new copy to the left. The multiset ${D(2), D(3)}$ is of size two.

我们来解释第一个包含四个测试用例的例子。

测试用例 1：($n = 2$, $k = 3$) 已在题目描述中说明。

参见下方该模拟过程的示意图。每条不同颜色的直线代表一个不同粒子的运动路径。如图所示，多重集中共有四个互异的粒子。注意：反射粒子之间的垂直间距仅为视觉清晰起见（如前所述，任意两个互异粒子之间不会发生碰撞）。

测试用例 2：($n = 2$, $k = 2$) 的解释如下：

1. 第一个平面在左侧产生一个 $D(1)$，同时允许 $D(2)$ 继续向右传播；
2. 第二个平面在左侧产生一个 $D(1)$，同时允许 $D(2)$ 继续向右传播；
3. 第一个平面允许 $D(1)$ 继续向左传播（$D(1)$ 无法再产生任何副本）。

最终所得多重集 ${D(1), D(1), D(2)}$ 的大小为三。

测试用例 3：($n = 3$, $k = 1$)，共有三个平面，但衰变年龄仅为 1。因此，当唯一一个粒子穿过各平面时，不会产生任何新副本。故答案为 1。

测试用例 4：($n = 1$, $k = 3$)，仅有一个平面。该粒子在平面左侧产生一个新副本。多重集 ${D(2), D(3)}$ 的大小为二。