{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\nRecently, Little Sub is obsessed with a game called Zuma.\n\u003c/p\u003e\nIn this game, players have a chain of $N$ energy balls, in which a demon called BaoBao lives. Initially, BaoBao stays in the $K$-th upmost ball. Due to the restriction of gravity, the length of a chain could not exceed $M$.\n\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\nAt each time unit, one of the two events will happen randomly. Let\u0027s denote $L$ as the length of the chain currently. With a possibility of $p_{insert}\u003d1-\\frac{L}{M}$, a ball will be inserted into the chain; With a possibility of $p_{break} \u003d \\frac{L}{M}$, the chain will be broken at a position.\n\u003c/p\u003e\n\u003cp\u003e\nMore specifically,\n\u003c/p\u003e\u003cul\u003e\n \u003cli\u003eWhen an energy ball is inserted, it can be inserted between any two adjacent energy balls or at one of the ends, each position has the possibility of $p \u003d \\frac{1}{L+1}$;\u003c/li\u003e\n \u003cli\u003eWhen the chain breaks, it could be cut between any two adjacent energy balls, each has the possibility of $p \u003d \\frac{1}{L-1}$. After breaking the chain into two segments, the segment NOT containing BaoBao will be discarded.\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e\u003c/p\u003e\n\n\u003cp\u003e\nNormally, BaoBao will never change its place. However, whenever BaoBao stays in the first ball or the last ball of the chain, it will escape from the chain and leak some energy. The amount of energy leakage is equal to the length of the chain when BaoBao escapes.\n\u003c/p\u003e\n\n\u003cp\u003e\nGiven $N$, $K$, and $M$, please calculate the expected amount of energy leakage.\n\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003e\nThere are multiple test cases. The first line of the input contains an integer $T$ ($1 \\le T \\le 1000$), indicating the number of test cases. For each test case:\n\u003c/p\u003e\n\u003cp\u003e\nThe first and only line contains three integers $N$, $K$ and $M$ ($1 \\le K \\le N \\le M \\le 250$).\n\u003c/p\u003e\n\u003cp\u003e\nIt\u0027s guaranteed that at most 10 test cases have $M \\gt 20$.\n\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003e\nFor each test case, output a single integer on a single line, indicating the expected amount of energy leakage. If the answer is $\\frac{A}{B}$, please print $C(0\\leq C\u0026lt;10^9+7)$ where $A\\equiv C\\times B\\pmod{10^9+7}$.\n\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\u003e5\r2 1 2\r2 2 10\r3 2 3\r3 2 5\r10 4 20\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r2\r2\r941659828\r196683114\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003eFor the first and the second test case, without any change to the chain, the demon will escape immediately.\u003c/p\u003e\n\u003cp\u003eFor the third test case, the chain can only break at a position, which renders the demon escape then.\u003c/p\u003e\n\u003cp\u003eFor the fourth case, things seem to be a little more complicated, because the chain can be longer and then be broken again.\u003c/p\u003e"}}]}