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).

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.

见题面 Input 部分

见题面 Output 部分

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.