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

6 3 

16

6 4 

26

8 8  

128