Bạn được cho bốn số nguyên \(n\), \(k\), \(l\) và \(h\).

Yêu cầu: Bạn hãy tính số cách chia \(n\) viên kẹo giống nhau cho \(k\) người khác nhau sao cho mỗi người nhận được ít nhất \(l\) viên kẹo và nhiều nhất \(h\) viên kẹo.

Hai cách được xem là khác nhau khi một người bất kỳ có số kẹo trong cách này khác với trong cách kia.

Input

• Chứa số bốn số nguyên \(n\), \(k\), \(l\) và \(h\) \((1 \le n, k \le 10^7, 0 \leq l \leq h \leq n)\).

Output

• Chứa một số nguyên là đáp án của bài toán khi chia lấy dư cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \leq 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \leq 10^3\).
• Subtask \(3\) (\(40\%\) số điểm): \(n \leq 10^6\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

6 2 2 6

3