Cứ vào mùa hè hằng năm, trường \(NKT\) sẽ tổ chức một buổi giao lưu ngoại khóa giữa các trường trong thành phố, và các trò chơi đồng đội là thứ không thể nào thiếu. Có \(n\) học sinh đến từ \(m\) trường khác nhau sẽ tham gia các trò chơi năm nay. Các học sinh sẽ đứng xếp hàng theo thứ tự đánh số từ \(1\) tới \(n\). Ban tổ chức dự định sẽ chia các học sinh thành một số đội từ \(n\) học sinh, mỗi học sinh thuộc đúng duy nhất một đội và một đội phải có tối thiểu một học sinh.

Để cho đơn giản, họ sẽ tách hàng đang đứng hiện tại thành một hoặc một số hàng liên tiếp và mỗi hàng sau khi tách như thế sẽ là một đội. Tuy nhiên, một đội không thể có học sinh thuộc quá nhiều trường khác nhau, bởi như thế thì các thầy cô sẽ rất khó quản lý. Mặt khác, một đội cũng không thể có học sinh thuộc quá ít trường khác nhau, bởi khi đó thì các bạn sẽ chỉ chơi với những người cùng trường, gây chia rẽ nội bộ và gây khó khăn cho các học sinh trong việc làm quen với những bạn mới trong đội mình. Sau khi cân nhắc kỹ càng, ban tổ chức quyết định một đội sẽ có các thành viên thuộc tối thiểu \(l\) trường khác nhau và tối đa \(r\) trường khác nhau.

Tuy ràng buộc phức tạp như vậy, nhưng vẫn có rất nhiều cách khác nhau để xếp đội, vì vậy bạn hãy giúp ban tổ chức tính số cách xếp đội khác nhau nhé. Lưu ý là có thể xếp thành một đội duy nhất gồm cả \(n\) thí sinh.

Input

• Dòng đầu tiên chứa các số nguyên \(n,m,l,r(1 \leq m \leq n \leq 10^6)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n(1 \leq a_i \leq m)\) với \(a_i\) là trường của học sinh thứ \(i\).

Output

Một dòng duy nhất chứa số cách xếp đổi. Kết quả chia lấy dư cho \(19122007\)

Subtask

• Subtask \(1(30\%)\): \(n \leq 10\).
• Subtask \(2(20\%)\): \(n \leq 100\).
• Subtask \(3(20\%)\): \(n \leq 10^3\).
• Subtask \(4(30\%)\): \(n \leq 10^6\).

6 6 1 1
1 2 3 4 5 6

1

6 6 6 6
1 2 3 4 5 6

1

9 4 2 3
1 2 4 3 2 2 1 3 4

6