TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

81.8% (9/11)

Submission's AC Ratio

16.3% (14/86)

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

6 3 2

Sample Output

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

For Testdata: 0 ~ 4, Score: 7
For Testdata: 5 ~ 9, Score: 9
For Testdata: 10 ~ 14, Score: 37
For Testdata: 15 ~ 19, Score: 47
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 1000 65536 262144
11 1000 65536 262144
12 1000 65536 262144
13 1000 65536 262144
14 1000 65536 262144
15 1000 65536 262144
16 1000 65536 262144
17 1000 65536 262144
18 1000 65536 262144
19 1000 65536 262144