dragonfruit

„Anul 1905, toamna”

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 \leq i \leq 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' \leq 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 consideră a fi distincte.

Cerință

Pentru a-și stabili planul de recoltare, Badinho este interesat de răspunsurile la următoarele întrebări:

• $q_1$: Care este numărul minim total de cactuși care ar trebui survolați într-un plan de recoltare?
• $q_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, \ldots, 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, \ldots, 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 $q1$ și $q2$ 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 \leq T \leq 5$
• $1 \leq K \leq 1 \ 000$
• $1 \leq S \leq 10$
• $0 \leq A_i \leq 1 \ 000$ pentru oricare $1 \leq i \leq N$

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.