1540 . 巨大史萊姆 (Gigantic Slime)
TopCoder
Description
史萊姆除了突變之外，還會融合為巨大的史萊姆。這在一個融合儀式中是常見不過的事情。
融合儀式通常都是在一環狀區域進行的。這一個環狀區域被分成$N$塊，順時針依序編號為$0$到$N-1$。對於參與儀式的$K$個史萊姆，他們會排好隊後，進入這個環狀區域的某一塊還沒有史萊姆的區塊。進到環狀區域後，他會和與他相鄰的史萊姆(如果有的話)融合為一隻更大的史萊姆，佔據著融合前這些史萊姆佔據的總區塊。
你，準備融合出超巨大史萊姆的遊戲管理員，想要讓$K$個史萊姆參與融合儀式。然而你不希望過程中有超過$G$隻史萊姆，以免魔力崩潰。請問，你有幾種進行儀式的方法？
(註1：$K$隻史萊姆最終不一定要融合為一隻史萊姆)
(註2：對於兩種進行儀式的方法，只要有一個$1\leq i\leq K$使得第$i$隻進入環狀區域的史萊姆所進入的區塊編號不同，即被視為不同的方法)
Input Format
每筆測資只包含一行，內含三個正整數$2\leq N\leq 10^ 9, 1\leq K\leq N, 1\leq G\leq \min(2000,K)$，分別代表環狀區域被分成幾塊，參與儀式的史萊姆個數以及史萊姆個數上限。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $N\leq 11$ | 7 |
| 2 (5~9) | $N\leq 20$ | 9 |
| 3 (10~14) | $N\leq 2000$ | 37 |
| 4 (15~19) | $N>2000,G\leq 100$ | 47 |
Output Format
輸出一個非負整數，代表進行儀式的方法數。由於答案很大，請將答案模$10^ 9+7$後輸出。
Sample Input 1
6 3 2
Sample Output 1
108
Hints
在隨便讓三隻史萊姆進入環狀區域的120種方法中，只有(0,2,4)(0,4,2)(2,0,4)(2,4,0)(4,0,2)(4,2,0)(1,3,5)(1,5,3)(3,1,5)(3,5,1)(5,1,3)(5,3,1)這12種方法不符合條件。
Problem Source
Problem set / Description by Paupière
建國中學105學年度校內第四次模擬賽pD
題目取自2015 TOI第二階段選訓第三次模擬考pA
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 7 |
| 2 | 5~9 | 9 |
| 3 | 10~14 | 37 |
| 4 | 15~19 | 47 |