Lưu ý:

• Ngày 2 sẽ diễn ra trên nền tảng RCOJ.
• Khuyến khích các bạn sử dụng cùng tên username tại cả hai nền tảng, các bạn sẽ không cần thực hiện xác thực gì thêm.
• Nếu các bạn sử dụng hai tài khoản khác nhau, các bạn hãy inbox page để thực hiện xác thực trước ~23:59~ ngày ~02/11/2025~.

Tại thành phố Alpha có một quán ăn khá nổi tiếng. Quán có ~N~ món được bày trên ~N~ bàn; bàn thứ ~i~ đặt món loại ~A_i~. Tuấn và Thái là hai nhân viên duy nhất làm cho quán ăn này. Một buổi tối, có ~M~ đơn hàng trên Shopee Food. Đơn hàng thứ ~i~ yêu cầu ~U_i~ món ăn loại ~V_i~.

Chủ quán phân công như sau:

• Chia dãy ~A_1, A_2, \dots, A_N~ thành ~2~ đoạn liên tiếp, bao phủ toàn bộ dãy và theo đúng thứ tự Tuấn quản lí đoạn bên trái, Thái quản lí đoạn bên phải. Một số nhân viên có thể nhận đoạn rỗng.
• Mỗi đơn hàng có thể giao cho tối đa một nhân viên. Một đơn hàng được coi là hoàn thiện nếu đoạn của nhân viên được giao có ít nhất ~U_i~ lần xuất hiện của loại ~V_i~.
• Với mỗi loại món ~t~, mỗi nhân viên chỉ được nhận tối đa một đơn hàng có loại ~t~.

Chủ quán muốn biết hai giá trị sau:

• Số lượng đơn hàng lớn nhất có thể hoàn thiện khi chủ quán phân chia tối ưu.
• Số cách phân chia và gán đơn hàng đạt được số lượng lớn nhất đó. Hai cách được coi là khác nhau nếu khác vị trí chia đoạn, hoặc khác cách gán đơn hàng cho nhân viên. Hãy lấy kết quả theo modulo ~10^9 + 7~.

Yêu cầu: Hãy giúp chủ quán tìm ra số đơn hàng lớn nhất và số cách phân công đạt được số đơn hàng đó.

INPUT

• Dòng đầu tiên chứa số nguyên ~\theta~ (~1\le \theta \le 6~) - số thứ tự của subtask chứa test này.
• Dòng thứ hai gồm hai số nguyên dương ~N, M~ (~1 \le N, M \le 2\times 10^5~).
• Dòng thứ ba gồm ~N~ số nguyên ~A_1, A_2, \dots, A_N~ (~1 \le A_i \le N~) - loại món trên từng bàn.
• ~M~ dòng tiếp theo: mỗi dòng gồm hai số nguyên dương ~U_i, V_i~ (~1 \le U_i, V_i \le N~) - yêu cầu của đơn hàng thứ ~i~.

Dữ liệu đảm bảo không tồn tại ~1\le i < j \le M~ sao cho ~V_i = V_j~ và ~U_i = U_j~.

OUTPUT

Ghi ra hai số nguyên:

• Số đơn hàng tối đa có thể hoàn thiện.
• Số cách phân chia và gán đơn hàng đạt tối đa, lấy modulo ~10^9 + 7~.

Nếu như bạn chỉ tìm được số đơn hàng tối đa thì bạn sẽ nhận được ~20\%~ số điểm test đó.

SUBTASKS

SAMPLE INPUT 1

1
8 3
1 3 2 1 2 3 3 2
1 1
2 2
3 3

SAMPLE OUTPUT 1

3 5

Trong ví dụ ~1~, ta có ~4~ cách phân đoạn như sau: ~[1, 3, 2, 1, 2, 3, 3, 2] []~

~[] [1, 3, 2, 1, 2, 3, 3, 2]~

~[1] [3, 2, 1, 2, 3, 3, 2]~

~[1, 3, 2, 1, 2, 3, 3] [2]~

Trong đó có cách thứ ~3~ có hai cách phân chia các đơn hàng:

• Cách 1: đơn hàng ~1~ cho người thứ nhất, đơn hàng ~2,3~ cho người thứ hai.
• Cách 2: đơn hàng ~1,2,3~ cho người thứ hai.

Các cách còn lại đều chỉ có một cách phân chia.

SAMPLE INPUT 2

1
8 6
1 1 2 2 1 2 2 1
3 1
2 1
5 1
3 2
1 2
2 2

SAMPLE OUTPUT 2

3 16