{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"Section1\"\u003e\r\n\t\u003cdiv align\u003d\"center\"\u003e\r\n\t\t\u0026nbsp;\u003c/div\u003e\r\n\t\u003cp class\u003d\"ListParagraph\"\u003e\r\n\t\t\u003cspan style\u003d\"font-size: 12pt; line-height: 115%; font-family: Garamond;\"\u003e\u003co:p\u003e\u0026nbsp;\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align: justify;\"\u003e\r\n\t\t\u003cspan style\u003d\"\"\u003eConsider this sequence {1, 2, 3, \u0026hellip; , N}, as a initial sequence of first \u003cb\u003eN\u003c/b\u003e natural numbers. You can rearrange this sequence in many ways. There will be \u003cb\u003eN!\u003c/b\u003e different arrangements. You have to calculate the number of arrangement of first \u003cb\u003eN\u003c/b\u003e natural numbers, where in first \u003cb\u003eM \u003c/b\u003e(M\u0026lt;\u003dN) positions, exactly \u003cb\u003eK \u003c/b\u003e(K\u0026lt;\u003dM) numbers are in its initial position.\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align: justify;\"\u003e\r\n\t\t\u003cspan style\u003d\"\"\u003e\u003co:p\u003e\u0026nbsp;\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align: justify;\"\u003e\r\n\t\t\u003cspan style\u003d\"\"\u003eExample:\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align: justify;\"\u003e\r\n\t\t\u003cspan style\u003d\"\"\u003e\u003co:p\u003e\u0026nbsp;\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align: justify;\"\u003e\r\n\t\t\u003cspan style\u003d\"\"\u003eFor, N \u003d 5, M \u003d 3, K \u003d2\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align: justify;\"\u003e\r\n\t\t\u003cspan style\u003d\"\"\u003e\u003co:p\u003e\u0026nbsp;\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align: justify;\"\u003e\r\n\t\t\u003cspan style\u003d\"\"\u003eYou should count this arrangement {1, 4, 3, 2, 5}, here in first 3 positions 1 is in 1\u003csup\u003e\u003cspan data-scayt_word\u003d\"st\" data-scaytid\u003d\"1\"\u003est\u003c/span\u003e\u003c/sup\u003e position and 3 in 3\u003csup\u003erd\u003c/sup\u003e position. So exactly 2 of its first 3 are in there initial position. \u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align: justify;\"\u003e\r\n\t\t\u003cspan style\u003d\"\"\u003e\u003co:p\u003e\u0026nbsp;\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\" style\u003d\"text-align: justify;\"\u003e\r\n\t\t\u003cspan style\u003d\"\"\u003eBut you should not count this {1, 2, 3, 4, 5}.\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u003cb\u003e\u003co:p\u003e\u0026nbsp;\u003c/o:p\u003e\u003c/b\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u003cb\u003e\u003cspan style\u003d\"font-size: 16pt; font-family: Arial;\"\u003eInput\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/b\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u003cspan style\u003d\"\"\u003eThe first line of input is an integer \u003cb\u003eT(T\u0026lt;\u003d1000)\u003c/b\u003e that indicates the number of test cases. Next T line contains 3 integers each, \u003cb\u003eN(1\u0026lt;\u003dN\u0026lt;\u003d1000),\u003c/b\u003e \u003cb\u003eM\u003c/b\u003e, and \u003cb\u003eK\u003c/b\u003e. \u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u003cb\u003e\u003cspan style\u003d\"font-size: 16pt;\"\u003e\u003co:p\u003e\u0026nbsp;\u003c/o:p\u003e\u003c/span\u003e\u003c/b\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u003cb\u003e\u003cspan style\u003d\"font-size: 16pt; font-family: Arial;\"\u003eOutput\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/b\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u003cspan style\u003d\"\"\u003eFor each case, output the case number, followed by the answer modulo \u003cb\u003e1000000007\u003c/b\u003e. Look at the sample for clarification.\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/p\u003e\r\n\t\u003ch1 align\u003d\"left\" style\u003d\"text-align: left;\"\u003e\r\n\t\t\u003cb\u003e\u003cspan style\u003d\"font-size: 16pt; font-style: normal;\"\u003e\u003co:p\u003e\u0026nbsp;\u003c/o:p\u003e\u003c/span\u003e\u003c/b\u003e\u003c/h1\u003e\r\n\t\u003ch1 align\u003d\"left\" style\u003d\"text-align: left;\"\u003e\r\n\t\t\u003cb\u003e\u003cspan style\u003d\"font-size: 16pt; font-family: Arial; font-style: normal;\"\u003eSample Input\u003cspan style\u003d\"\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003c/span\u003eOutput for Sample Input\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/b\u003e\u003c/h1\u003e\r\n\t\u003ctable border\u003d\"1\" cellpadding\u003d\"0\" cellspacing\u003d\"0\" class\u003d\"MsoNormalTable\" style\u003d\"border: medium none ; background: rgb(204, 204, 204) none repeat scroll 0% 0%; -moz-background-clip: -moz-initial; -moz-background-origin: -moz-initial; -moz-background-inline-policy: -moz-initial; border-collapse: collapse;\"\u003e\r\n\t\t\u003ctbody\u003e\r\n\t\t\t\u003ctr style\u003d\"\"\u003e\r\n\t\t\t\t\u003ctd style\u003d\"border: 1pt solid windowtext; padding: 0in 5.4pt; width: 3.2in;\" valign\u003d\"top\" width\u003d\"307\"\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t\u003cb style\u003d\"\"\u003e\u003cspan style\u003d\"font-family: \u0026quot;Courier New\u0026quot;;\"\u003e1\u003cbr /\u003e\r\n\t\t\t\t\t\t5 3 2\u003cbr style\u003d\"\" /\u003e\r\n\t\t\t\t\t\t\u003c!--[if !supportLineBreakNewLine]--\u003e\u003c!--[endif]--\u003e\u003cbr style\u003d\"\" /\u003e\r\n\t\t\t\t\t\t\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/b\u003e\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\t\u003ctd style\u003d\"border-style: solid solid solid none; border-color: windowtext windowtext windowtext -moz-use-text-color; border-width: 1pt 1pt 1pt medium; padding: 0in 5.4pt; width: 231.85pt;\" valign\u003d\"top\" width\u003d\"309\"\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\t\t\t\t\u003cb style\u003d\"\"\u003e\u003cspan style\u003d\"font-family: \u0026quot;Courier New\u0026quot;;\"\u003eCase \u003cst1:time hour\u003d\"13\" minute\u003d\"12\" w:st\u003d\"on\"\u003e1: 12\u003c/st1:time\u003e\u003co:p\u003e\u003c/o:p\u003e\u003c/span\u003e\u003c/b\u003e\u003c/p\u003e\r\n\t\t\t\t\t\u003cp class\u003d\"MsoNormal\" style\u003d\"\"\u003e\r\n\t\t\t\t\t\t\u003cb\u003e\u003cspan style\u003d\"font-family: \u0026quot;Courier New\u0026quot;;\"\u003e\u003co:p\u003e\u0026nbsp;\u003c/o:p\u003e\u003c/span\u003e\u003c/b\u003e\u003c/p\u003e\r\n\t\t\t\t\u003c/td\u003e\r\n\t\t\t\u003c/tr\u003e\r\n\t\t\u003c/tbody\u003e\r\n\t\u003c/table\u003e\r\n\t\u003cdiv align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"text-align: center;\"\u003e\r\n\t\t\u003chr align\u003d\"center\" size\u003d\"2\" width\u003d\"100%\" /\u003e\r\n\t\u003c/div\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u003co:p\u003e\u0026nbsp;\u003c/o:p\u003e\u003c/p\u003e\r\n\t\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\t\u003co:p\u003e\u0026nbsp;\u003c/o:p\u003e\u003c/p\u003e\r\n\t\u003cp align\u003d\"center\" class\u003d\"MsoNormal\" style\u003d\"text-align: center;\"\u003e\r\n\t\t\u003co:p\u003e\u0026nbsp;\u003c/o:p\u003e\u003c/p\u003e\r\n\u003c/div\u003e"}}]}