Một nhóm có \(n\) người bạn, các bạn được đánh số hiệu từ \(1\) đến \(n\). Mọi người dự định tất cả đứng thành một hàng ngang để cùng nhau chụp ảnh. Đánh số \(n\) vị trí đứng từ trái sang phải bắt đầu từ \(1\) đến \(n\). Với một số nguyên dương \(k\), khi xếp hàng ai cũng mong muốn chênh lệch giữa số hiệu của mình với vị trí đứng không vượt quá \(k\).

Yêu cầu

• Cho hai số nguyên dương \(n, k\), hãy đếm số cách xếp \(n\) người vào \(n\) vị trí để chụp ảnh sao cho người có số hiệu \(i\) (với \(1 \le i \le n\)) xếp vào vị trí \(j\) (với \(1 \le j \le n\)) thì \(|i - j| \le k\).

Dữ liệu vào

• Vào từ thiết bị vào chuẩn gồm hai số nguyên dương \(n, k\) \((1 \le n \le 10^9, k \lt 5)\).

Dữ liệu ra

• Một dòng chứa một số là phần dư của kết quả tính được chia dư cho \((10^9 + 7)\).

Ràng buộc:

• Subtask 1 (25%): \(n \le 8\);
• Subtask 2 (25%): \(n \le 10^5, k = 1\);
• Subtask 3 (25%): \(n \le 10^5\);
• Subtask 4 (15%): \(k \lt 3\);
• Subtask 5 (10%): Không có ràng buộc gì thêm.

Input 1

3 1

Output 1

3

Input 2

3 2

Output 2

6