Cu ajutorul tău, Badinho a primit subvenția de la stat, iar construcția rutei a fost finalizată în timp record. Datorită succesului, acesta a decis sa își deschidă o nouă afacere în Ciudad de México. Pe plaiurile deținute de primăria orașului crește o specie rară de cactus, care la maturitate va da roade fructe pitahaya, cunoscute și sub denumirea de “dragon fruits”.

Câmpul deținut de primărie are forma unui rând de N cactuși, dispuși de la stânga la dreapta, numerotați de la 1 la N. Notăm cu A[i] pentru 1 ≤ i ≤ N numărul de fructe coapte din cactusul i. El Alcalde (primarul) dorește să recolteze exact K fructe de pe câmp, așa că a contractat firma lui Badinho.

Din motive logistice, recoltarea cactușilor se va realiza în cel mult S etape. Într-o etapă, drona care recoltează fructele va survola o singură parcelă de cactuși și va culege toate fructele coapte din cactușii survolați. O parcelă este definită ca o subsecvență de cactuși. De exemplu, parcela [6, 9] este formată din cactușii 6, 7, 8 și 9. Pentru a nu deranja populația de cactuși, fiecare cactus poate fi survolat cel mult o dată pe parcursul întregii operațiuni de recoltare. A survola o parcelă înseamnă a survola toți cactușii din parcela respectivă.

Pentru a planifica cât mai bine recoltarea fructelor, Badinho trebuie să-și facă un plan de recoltare. Mai exact, un astfel de plan constă dintr-un număr S' ≤ S de etape de recoltare care vor fi efectuate și din parcelele care vor fi survolate la fiecare din cele S' etape. Două planuri de recoltare se consideră diferite dacă există cel puțin o parcelă survolată într-o etapă a unuia dintre ele care să nu fie survolată și în vreo etapă a celuilalt. De exemplu, dacă într-un plan format din două etape se survolează parcela [1, 2], urmată de parcela [3, 4], iar în alt plan format din două etape se survolează parcela [3, 4], urmată de parcela [1, 2], atunci planurile se consideră identice. În schimb, dacă într-un plan cu o singură etapă se survolează parcela [1, 2], iar în alt plan format din două etape se survolează parcelele [1, 1] și [2, 2], atunci planurile se consideră distincte. Un alt exemplu este că dacă într-un plan format din două etape se survolează parcela [1, 3], urmată de parcela [4,4], iar în alt plan format din două etape se survolează parcela [1, 2], urmată de parcela [3, 4], atunci planurile se considera a fi distincte.

Cerința

Pentru a-și stabili planul de recoltare, Badinho este interesat de răspunsurile la următoarele întrebări:
1) Care este numărul minim total de cactuși care ar trebui survolați într-un plan de recoltare?
2) Câte planuri de recoltare în care se survolează un număr minim de cactuși există? Deoarece acest număr poate fi foarte mare, se cere doar valoarea sa modulo 1.000.000.007.

Badinho își dorește să afle raspunsurile la cele două întrebări într-un număr T de scenarii. Un scenariu este determinat de valorile N, K, S, A[1], A[2], …, A[N].

Date de intrare

Pe prima linie a fișierului dragonfruit.in se află numărul T, urmat de cele T scenarii, fiecare în următorul format:

• pe prima linie numerele naturale N, K, S, separate prin spații;
• pe a doua linie numerele A[1], A[2], …, A[N] separate prin spații.

Date de ieșire

Pentru fiecare scenariu dintre cele T se va afișa câte o linie în fișierul de ieșire dragonfruit.out care va conține două numere naturale separate printr-un spațiu reprezentând, în ordine, răspunsurile la cerințele 1 și 2 din enunț pentru scenariul curent. În cazul în care, pentru un anumit scenariu, nu există niciun plan de recoltare care să satisfacă cerințele date, se va afișa 0 0 pe linia respectivă.

Restricții și precizări

• 1 ≤ T ≤ 5
• 1 ≤ K ≤ 1000
• 1 ≤ S ≤ 10
• 0 ≤ A[i] ≤ 1000 pentru oricare 1 ≤ i ≤ N.
• Pentru 4 puncte, S=1 și 1 ≤ N ≤ 2000
• Pentru 7 puncte, S=2 și 1 ≤ N ≤ 100
• Pentru 9 puncte, S=3 și 1 ≤ N ≤ 50
• Pentru 10 puncte, S=1 și 1 ≤ N ≤ 100.000
• Pentru 13 puncte, S=2 și 1 ≤ N ≤ 2000
• Pentru 23 puncte, 1 ≤ N ≤ 70
• Pentru 34 puncte, 1 ≤ N ≤ 2000

Exemplu:

dragonfruit.in

4
8 7 4
2 1 0 1 0 2 1 99
2 99 10
50 50
3 8 1
1 8 1
5 3 2
2 1 2 1 1

dragonfruit.out

5 3
0 0
1 1
2 9

Explicație

Scenariul 1
Următoarele planuri de recoltare recoltează 7 dragon fruits survolând un număr minim de cactuși:

• Planul 1: [1, 2], [4, 4], [6, 7];
• Planul 2: [1, 1], [2, 2], [4, 4], [6, 7];
• Planul 3: [1, 2], [4, 4], [6, 6], [7, 7].

Observați că planul de recoltare [1, 3], [4, 4], [6, 7] nu se consideră valid, deoarece se survolează un număr de 6 cactuși, care nu este minim, chiar dacă s-au cules K=7 dragon fruits.

Scenariul 2
Nu există niciun plan de recoltare în care să fie recoltate 99 dragon fruits.

Scenariul 3
Există un singur plan de recoltare în care să fie recoltate 8 dragon fruits: [2, 2].

Scenariul 4
Următoarele planuri de recoltare recoltează 3 dragon fruits survolând un număr minim de 2 cactuși:

• Planul 1: [1, 2];
• Planul 2: [2, 3];
• Planul 3: [3, 4];
• Planul 4: [1, 1], [2, 2];
• Planul 5: [1, 1], [4, 4];
• Planul 6: [1, 1], [5, 5];
• Planul 7: [2, 2], [3, 3];
• Planul 8: [3, 3], [4, 4];
• Planul 9: [3, 3], [5, 5].

Observați că planul de recoltare [2, 2], [4, 4], [5, 5] nu se consideră valid, deoarece se survolează un număr de 3 cactuși, care nu este minim, chiar dacă s-au cules K=3 dragon fruits.