Sắp xếp binh lính

Nhà vua triệu tập \(N\) binh lính đứng thành một hàng. Mỗi vị trí có thể là binh lính loại \(A\) hoặc \(B\). Nhà
vua yêu cầu rằng trong hàng không được xuất hiện \(K\) binh lính loại \(A\) đứng cạnh nhau (tức không có
đoạn gồm đúng \(K\) ký tự \('A'\) liên tiếp).

Hãy tính số cách sắp xếp \(N\) binh lính thỏa mãn điều kiện trên. Kết quả lấy modulo \(10^9 + 7\).

Input

Dữ liệu vào SOLDIERS.INP:

• Một dòng chứa hai số nguyên dương \(n, k\) \((1 \leq k \leq n \leq 10^6)\).

Output

Dữ liệu ra SOLDIERS.OUT:

• Một số nguyên không âm duy nhất --- số cách sắp xếp, modulo \(10^9 + 7\).

Example

3 3

7

Scoring

• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(n \leq 20\).
• Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(20 < n \leq 1000\).
• Có \(40\%\) số test tương ứng với \(40\%\) số điểm có \(1000 < n \leq 10^6\).