Tô sân

Một khu vườn hình chữ nhật được lát bởi \(n\) viên gạch xếp thành một hàng ngang. Ban tổ chức lễ hội muốn sơn lại các viên gạch này bằng hai màu: vàng hoặc cam.

Để tạo hiệu ứng đẹp mắt, ban tổ chức yêu cầu rằng giữa bất kỳ hai viên gạch được sơn màu cam, khoảng cách giữa chúng không nhỏ hơn \(k\) (tức là nếu hai viên ở vị trí \(i\) và \(j\) cùng màu cam thì \(|i - j| \ge k\)).

Hỏi có bao nhiêu cách để sơn \(n\) viên gạch, sao cho mỗi viên gạch được tô một trong hai màu, và điều kiện trên được thỏa mãn?

Input

Một dòng gồm hai số nguyên \(n\) và \(k\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le k \le n\)).

Output

In ra một số nguyên là số cách sơn thỏa mãn, modulo \(10^9 + 7\).

Scoring

• Có \(30\%\) số điểm ứng với \(n \le 20\).

• Có \(30\%\) số điểm ứng với \(n \le 1000\).

• \(40\%\) số điểm còn lại không có ràng buộc gì thêm.

Notes

Với \(n = 4\), \(k = 2\), có \(8\) cách sơn như sau (o: cam, y: vàng):

• oyyy

• yoyy

• yyoy

• oyoy

• oyyo

• yoyo

• yyyo

• yyyy