Chia nhóm

Mùa hè này, ban tổ chức muốn chia \(n\) học sinh (đứng theo thứ tự từ \(1\) đến \(n\)) thành các đội để tham gia trò chơi.
Học sinh thứ \(i\) đến từ trường \(a_i\) \((1 \le a_i \le m)\).

Mỗi đội phải gồm một đoạn liên tiếp các học sinh trong hàng.
Một đội được gọi là hợp lệ nếu số lượng trường khác nhau xuất hiện trong đội đó nằm trong đoạn \([L, R]\).

Yêu cầu. Với mỗi trường hợp, hãy tính số cách chia toàn bộ \(n\) học sinh thành các đội hợp lệ (có thể chỉ có một đội gồm tất cả \(n\) học sinh).
Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho \(918052004\).

Input

• Dòng đầu chứa số nguyên \(t\) \((1 \le t \le 10)\) là số lượng test.
• Mỗi test gồm: - Một dòng chứa bốn số nguyên \(n, m, L, R\) \((1 \le L \le R \le m \le n \le 180504)\). - Một dòng chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) \((1 \le a_i \le m)\).

Output

• In ra \(t\) dòng, mỗi dòng là số cách chia đội của test tương ứng, lấy modulo \(918052004\).

Input

%
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

Output

%
1
1
6

Notes

Một cách chia đội tương ứng với việc chọn một số vị trí cắt để tạo ra các đoạn liên tiếp.
Mỗi đoạn phải có số lượng trường khác nhau nằm trong \([L, R]\).
Ta cần đếm tổng số cách chia thỏa mãn điều kiện trên cho toàn bộ dãy.

Scoring

• (30%) \(n \le 15\);
• (20%) \(n \le 185\);
• (20%) \(n \le 1805\);
• (30%) Không có ràng buộc thêm.