Beautiful Pairs of Numbers

题意翻译

给定两个数 $n,k$，对于整数对序列 $(a_1,b_1),\cdots,(a_k,b_k)$，如果满足 $1\leq a_1\leq b_1\lt a_2\leq b_2\lt\cdots\lt a_k\leq b_k\leq n$ 且所有的 $b_i-a_i$ 互不相同，则称这个序列是**美丽的**，求**美丽的**序列的个数。

题目描述

The sequence of integer pairs $ (a_{1},b_{1}),(a_{2},b_{2}),...,(a_{k},b_{k}) $ is beautiful, if the following statements are fulfilled: - $ 1<=a_{1}<=b_{1}&lt;a_{2}<=b_{2}&lt;...&lt;a_{k}<=b_{k}<=n $ , where $ n $ is a given positive integer; - all numbers $ b_{1}-a_{1} $ , $ b_{2}-a_{2} $ , $ ... $ , $ b_{k}-a_{k} $ 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 $ $ (10^{9}+7) $ .

输入输出格式

输入格式

The first line contains integer $ t $ ( $ 1<=t<=2·10^{5} $ ) — 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 $ $ (10^{9}+7) $ . Print the answers to the tests in the order in which the tests are given in the input.

输入输出样例

输入样例 #1

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

输出样例 #1

1
3
0
6
2
0

说明

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.