喔就是,總是有些人不好好一階一階上樓梯,偏要一次跳兩階對吧
還記得那個窮學生 sakura 嗎?
有人委託他去算從地板(第 0 階)開始,
每次可以只爬 1 階或直接跳 2 階,到第 $N$ 階樓梯有幾種爬法?
rainsn 是講求效率的人,他認為爬樓梯不是一定要快,但也不該總是慢,這樣在時間和體力間才能達到一個平衡
所以他多設下一個條件,在不超過 $k$ 次爬到 $N$ 階有幾種爬法?
輸入兩個正整數 $N, k$ $(1 \le k \le N \le 10^ 3)$
到第 $N$ 階樓梯且不超過 $k$ 次有幾種爬法
由於計算結果會很龐大,請輸出把結果除以 $10^9 + 9$ 後得到的餘數
No. | Testdata Range | Score |
---|---|---|
1 | 0~36 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 | |
14 | 1000 | 65536 | 65536 | |
15 | 1000 | 65536 | 65536 | |
16 | 1000 | 65536 | 65536 | |
17 | 1000 | 65536 | 65536 | |
18 | 1000 | 65536 | 65536 | |
19 | 1000 | 65536 | 65536 | |
20 | 1000 | 65536 | 65536 | |
21 | 1000 | 65536 | 65536 | |
22 | 1000 | 65536 | 65536 | |
23 | 1000 | 65536 | 65536 | |
24 | 1000 | 65536 | 65536 | |
25 | 1000 | 65536 | 65536 | |
26 | 1000 | 65536 | 65536 | |
27 | 1000 | 65536 | 65536 | |
28 | 1000 | 65536 | 65536 | |
29 | 1000 | 65536 | 65536 | |
30 | 1000 | 65536 | 65536 | |
31 | 1000 | 65536 | 65536 | |
32 | 1000 | 65536 | 65536 | |
33 | 1000 | 65536 | 65536 | |
34 | 1000 | 65536 | 65536 | |
35 | 1000 | 65536 | 65536 | |
36 | 1000 | 65536 | 65536 |