← 返回题目列表

Codeforces · 1498/C

C. 平面反射

中文机器翻译题面 查看原题

Gaurang 在一个神秘的宇宙中长大。他面对的是 $$$n$$$ 连续的 2D 平面。他向位面发射了一颗衰变年龄 $$$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)\}$$$。 (有关此测试用例的直观解释,请参阅注释。)

当飞机数量过多时,Gaurang 无法应对这种情况的复杂性。给定 $$$n$$$ 和 $$$k$$$,帮助 Gaurang 找到多重集 $$$S$$$ 的大小。

由于多重集的大小可能非常大,因此您必须以 $$$10^9+7$$$ 为模输出它。

注意:粒子可以在平面之间来回移动而不会相互碰撞。

输入

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

此外,所有测试用例的 $$$n$$$ 总和不会超过 $$$1000$$$,所有测试用例的 $$$k$$$ 总和不会超过 $$$1000$$$。一个测试中的所有测试用例都是不同的。

输出

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

示例

输入 #1

4
2 3
2 2
3 1
1 3

输出 #1

4
3
1
2

输入 #2

3
1 1
1 500
500 250

输出 #2

1
2
257950823

注意

让我们用四个测试用例来解释第一个示例。

测试用例 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$$$),有三个平面,但衰变年龄只有一个。因此,当一个粒子穿过平面时,不会产生新的副本。因此,答案是一。

测试用例 4:($$$n = 1$$$, $$$k = 3$$$) 只有一架飞机。粒子在左侧生成一个新副本。多重集 $$$\{D(2), D(3)\}$$$ 的大小为 2。