Cứ vào mùa hè hằng năm, trường chuyên Đ 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 số nguyên \(t\) \((1 \leq t \leq 10)\) là số lượng trường hợp. Mỗi trường hợp gồm:
  • Dòng đầu tiên chứa bốn số nguyên \(n\), \(m\), \(l\) và \(r\) \((1 \leq l \leq r \leq m \leq n \leq 180504)\), lần lượt là số học sinh tham gia, số trường, và hai số \(l\), \(r\) như mô tả của đề.
  • Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq m)\), với \(a_i\) là trường của học sinh thứ \(i\).

Output

• Gồm \(t\) dòng, mỗi dòng chứa một số nguyên duy nhất là số cách xếp đội của trường hợp tương ứng. Vì kết quả có thể rất lớn, hãy in phần dư của kết quả khi chia cho \(918052004\).

Scoring

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

Example

3
6 6 1 1
1 2 3 4 5 6
6 6 6 6
1 2 3 4 5 6
9 4 2 3
1 2 4 3 2 2 1 3 4

1
1
6