← 返回题目列表

Codeforces · 403/D

D. 美丽的数字对

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

如果满足以下语句,则整数对 (a1, b1), (a2, b2), ..., (ak, bk) 的序列很漂亮:

- 1 ≤ a1 ≤ b1 < a2 ≤ b2 < ... < ak ≤ bk ≤ n,其中n是给定的正整数;
- 所有数字 b1 - a1、b2 - a2、...、bk - ak 都是不同的。

对于给定的数字 n,找出长度为 k 的美丽序列的数量。由于答案可能相当大,因此打印除以 1000000007 (109 + 7) 后的余数。

输入

第一行包含整数 t (1 ≤ t ≤ 2·105) — 测试数据的数量。

接下来的 t 行每行包含两个整数 n 和 k (1 ≤ k ≤ n ≤ 1000)。

输出

对于输入中的每个测试,打印问题的答案以 1000000007 (109 + 7) 为模。按照输入中给出的测试顺序打印测试的答案。

示例

输入 #1

6
1 1
2 1
2 2
3 1
3 2
3 3

输出 #1

1
3
0
6
2
0

注意

在第一个测试样本中,恰好有一个漂亮的序列:(1, 1)。

在第二个测试样本中,以下序列很漂亮:

- (1, 1);
- (1, 2);
- (2, 2).

在第四个测试样本中,以下序列很漂亮:

- (1, 1);
- (1, 2);
- (1, 3);
- (2, 2);
- (2, 3);
- (3, 3).

在第五个测试样本中,以下序列很漂亮:

- (1, 1), (2, 3);
- (1, 2), (3, 3).

在第三个和第六个样本中,没有漂亮的序列。