#P403D. Beautiful Pairs of Numbers
-
ID: 5827
Type: RemoteJudge
3000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
Hydro
Tags> Beautiful Pairs of Numbers
No submission language available for this problem.
Description
The sequence of integer pairs (a1, b1), (a2, b2), ..., (ak, bk) is beautiful, if the following statements are fulfilled:
- 1 ≤ a1 ≤ b1 < a2 ≤ b2 < ... < ak ≤ bk ≤ n, where n is a given positive integer;
- all numbers b1 - a1, b2 - a2, ..., bk - ak are distinct.
For the given number n find the number of beautiful sequences of length k. As the answer can be rather large, print the remainder after dividing it by 1000000007 (109 + 7).
The first line contains integer t (1 ≤ t ≤ 2·105) — the number of the test data.
Each of the next t lines contains two integers n and k (1 ≤ k ≤ n ≤ 1000).
For each test from the input print the answer to the problem modulo 1000000007 (109 + 7). Print the answers to the tests in the order in which the tests are given in the input.
Input
The first line contains integer t (1 ≤ t ≤ 2·105) — the number of the test data.
Each of the next t lines contains two integers n and k (1 ≤ k ≤ n ≤ 1000).
Output
For each test from the input print the answer to the problem modulo 1000000007 (109 + 7). Print the answers to the tests in the order in which the tests are given in the input.
Samples
6
1 1
2 1
2 2
3 1
3 2
3 3
1
3
0
6
2
0
Note
In the first test sample there is exactly one beautiful sequence: (1, 1).
In the second test sample, the following sequences are beautiful:
- (1, 1);
- (1, 2);
- (2, 2).
In the fourth test sample, the following sequences are beautiful:
- (1, 1);
- (1, 2);
- (1, 3);
- (2, 2);
- (2, 3);
- (3, 3).
In the fifth test sample, the following sequences are beautiful:
- (1, 1), (2, 3);
- (1, 2), (3, 3).
In the third and sixth samples, there are no beautiful sequences.