如果满足以下语句,则整数对 (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).
在第三个和第六个样本中,没有漂亮的序列。