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

No. Testdata Range Score
1 0~4 7
2 5~9 9
3 10~14 37
4 15~19 47

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3
15 1000 65536 262144 4
16 1000 65536 262144 4
17 1000 65536 262144 4
18 1000 65536 262144 4
19 1000 65536 262144 4