Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cóc là loài vật có trí nhớ và khả năng định vị rất tốt. Khi bị bắt mang đi một nơi rất xa, cóc sẽ tự tìm thấy đường về nhà, bằng cách nào đó thì vẫn bí ẩn như cách con người tìm ra lửa vậy...

Kế hoạch của cóc là nhảy về nhà bằng đường chim bay, đường thằng, (hay cũng có thể gọi là đường cóc nhảy, tất nhiên rồi). Mỗi bước nhảy của nó có thể nhảy xa tùy ý nhưng khoảng cách phải là một số nguyên dương. Khoảng cách từ cóc về nhà đang là \(n\), nó không muốn nhảy quá \(k\) bước. Hãy giúp chú đếm số cách khác nhau để nhảy về nhà. Hai cách nhảy được coi là khác nhau nếu số bước nhảy khác nhau hoặc tồn tại \(i\) sao cho độ dài của bước nhảy thứ \(i\) trong cách này khác với trong cách kia

Input

  • Chứa hai số nguyên dương: \(n\) \(k\)

Output

  • In ra phần dư của số cách nhảy khi chia cho \(10^9+7\)

Scoring

  • Subtask \(1\): \(k \leq n \leq 10\)
  • Subtask \(2\): \(k \leq n \leq 1000\)
  • Subtask \(3\): \(k \leq n \leq 10^6\)

Example

Test 1

Input
6 3 
Output
16

Test 2

Input
6 4 
Output
26

Test 1

Input
8 8  
Output
128

Bình luận


  • 0
    huyhau6a2    9:53 a.m. 8 Tháng 7, 2022 chỉnh sửa 2

    Test có bị sai không ạ

    Test 1 đáng lẽ phải là 24 cách chứ ạ

    Update: đã hiểu đề và ac