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

Năm 2050, Clue Festival dự kiến sẽ được diễn ra ở sân vận động Tokyo Dome - một trong những sân vận động hàng đầu ở Châu Á.

Với mỗi mười phút, khán giả của một trong 4 fandom ~\in \{C, L, U, E\}~ sẽ cần giơ bảng hiệu của fandom mình để cổ vũ cho idol. Các thứ tự giơ bảng đã được ghi lại thành dãy ~a_1, a_2, ..., a_n~ với mỗi ~a_i~ là một trong bốn ký tự ~\{C, L, U, E\}~.

Một fandom ~i~ được gọi là "fandom ngôi sao" của đoạn ~[l, r]~ nếu số lần giơ bảng của fandom đó nhiều hơn từng fandom còn lại trong đoạn đó (hay nói cách khác, fandom ~i~ phải là mode duy nhất của đoạn đó mới tính là "fandom ngôi sao").

Yêu cầu: Với mỗi fandom, cần tìm kích thước lớn nhất của một đoạn con liên tiếp mà fandom đó là fandom ngôi sao của đoạn.

INPUT

Dòng đầu tiên chứa số nguyên dương ~n (1 \le n \le 10^5)~ là số lượt giơ bảng của tất cả các fandom.

Dòng thứ hai chứa ~n~ ký tự là một trong 4 ký tự ~\{C, L, U, E\}~.

OUTPUT

Gồm một dòng in ra 4 số nguyên, trong đó:

• Số nguyên thứ nhất là đáp số với fandom ~C~.
• Số nguyên thứ hai là đáp số với fandom ~L~.
• Số nguyên thứ ba là đáp số với fandom ~U~.
• Số nguyên cuối cùng là đáp số với fandom ~E~.

SUBTASKS

SAMPLE INPUT

7
CLEECUL

SAMPLE OUTPUT

1 1 1 5

Đoạn tương ứng với các fandom ~C~, ~L~, ~U~, ~E~ là ~[1, 1]~, ~[2, 2]~, ~[6, 6]~ và ~[2, 6]~.

huyhau6a2 có một băng số ~a~ gồm ~n~ số và dự định sẽ tặng cho một người bạn nhân dịp sinh nhật của bạn đó. Băng số này có tính chất rất đặc biệt, vì nếu cậu chọn bất kỳ số nguyên dương ~l~ nào từ ~1~ đến ~n~, thì cậu luôn có thể chọn ~l~ trong ~n~ số trên băng sao cho tổng các số cậu chọn chia hết cho ~3~.

Tuy nhiên, bằng một cách nào đó, duong3982 đã vẽ bậy lên băng số, giờ chỉ còn ~m~ số đầu tiên hiện rõ, còn lại thì không thể xác định được vì đã bị vẽ đè lên. huyhau6a2 giờ phải viết lại cho đủ ~n~ số trên băng nhưng vì có quá nhiều số nên cậu không thể nhớ rõ các số còn lại. Tuy nhiên, cậu biết rằng các số trên băng luôn là các số nguyên dương có giá trị từ ~1~ đến ~k~. Giờ cậu cần làm lại băng số, nhưng tự nhiên trong đầu lại nảy lên một bài toán: Với các điều kiện như trên, thì tồn tại bao nhiêu băng số thỏa mãn điều kiện mà cậu có thể tạo được?

Tất nhiên vì cậu còn phải làm cho xong quà sinh nhật nên bài toán này xin nhường lại các bạn!

INPUT

Dòng đầu tiên gồm một số nguyên dương ~t~ (~1 \le t \le 2 \times 10^4~) là số trường hợp thử nghiệm. Định dạng với mỗi trường hợp thử nghiệm được mô tả như sau:

• Dòng đầu tiên trong mỗi trường hợp thử nghiệm gồm ba số nguyên dương ~n, k, m~ (~1 \le n, k \le 10^{18}~, ~0 \le m \le min (n, 50)~).
• Dòng thứ hai trong mỗi trường hợp thử nghiệm gồm ~m~ số nguyên dương ~a_1, a_2, ..., a_m~ (~1 \le a_i \le k~) tương ứng với các số đầu tiên trên băng số của huyhau6a2. Trong trường hợp ~m = 0~ sẽ không có dòng này.

OUTPUT

In ra ~t~ dòng, dòng thứ ~i~ in ra duy nhất một số nguyên không âm là số lượng băng số huyhau6a2 có thể làm tương ứng với trường hợp thử nghiệm thứ ~i~. Vì kết quả có thể rất lớn nên bạn chỉ cần in ra kết quả sau khi chia lấy dư cho ~998244353~.

SUBTASKS

Gọi ~N~ là tổng ~n~ trong tất cả trường hợp thử nghiệm.

Số điểm của bạn cho mỗi test, sẽ tỷ lệ thuận với số test nhỏ bạn giải đúng. Lưu ý, bạn vẫn cần in đủ ~T~ dòng, nếu không, bạn có thể gặp lỗi Presentation Error.

SAMPLE INPUT

6
3 4 0
3 4 1
1
3 4 1
2
3 4 1
3
3 4 1
4
3 4 3
2 3 2

SAMPLE OUTPUT

13
2
4
5
2
0