D. Beautiful Pairs of Numberstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThe 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).InputThe 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).OutputFor 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.ExamplesInput61 12 12 23 13 23 3Output130620NoteIn 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.
Input61 12 12 23 13 23 3
Output130620
['combinatorics', 'dp', '*2300']