{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eSquark has a game machine, which has 2n slots in a row, numbered from 1 to 2n, inclusively. He plays a game with the machine for several rounds. In each round, he divides that row into k segments with marks at boundaries between adjacent segments. Each segment must contain an even number of slots. Then, the machine generates a random permutation of {1, 2, . . . , 2n} and displays the permutation on the slots.Finally, the machine calculates the inversion number of each segment and multiplies them together to get the score of the round. The inversion number of a sequence is the number of inversions (also called inversion pairs) in the sequence.\u003cbr\u003e\u003cbr\u003eSquark can play the game for as many rounds as he wants, but he must use different partitions in different rounds. Two partitions are considered to be different if there is a mark somewhere in one partition but not in the other. The total game score is simply the sum of the score of each round. However, the machine has been intruded by a malware, which changes the permutation before the machine calculates the score of each round. It picks each segment and sorts the numbers in the slots numbered with even numbers.\u003cbr\u003e\u003cbr\u003eFor example, if n \u003d 2, k \u003d 1 and the permutation generated is (2, 4, 1, 3). The malware will pick numbers 4 and 3 (because they are in slots numbered with 2 and 4) and sort them, changing the permutation into (2, 3, 1, 4). So Squark will get a score of 2 (pairs (2, 1) and (3, 1)) in this round. Squark wants to know the maximum expected game score he can get.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer T (T ≤ 10\u003csup\u003e4\u003c/sup\u003e) denoting the number of the test cases. For each test case, there is one line containing two integers, n(1 ≤ n ≤ 2000) and k(1 ≤ k ≤ n) as mentioned above."}},{"title":"Output","value":{"format":"HTML","content":"As the answer for the problem can be very large, please calculate it as an irreducible fraction A/B and output (A·B\u003csup\u003e-1\u003c/sup\u003e) mod (10\u003csup\u003e9\u003c/sup\u003e + 7) for each test case in a separate line. Here, B\u003csup\u003e-1\u003c/sup\u003e is the multiplicative inverse of B modulo 10\u003csup\u003e9\u003c/sup\u003e + 7. The input constraints guarantee that B and 10\u003csup\u003e9\u003c/sup\u003e + 7 are coprime, so this expression is properly defined."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n1 1\r\n2 2\r\n2 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e500000004\r\n250000002\r\n166666670\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"The maximum expected game scores in the example are 1/2, 1/4, 13/6 respectively."}}]}