Fişierul intrare/ieşire:	tripar.in, tripar.out	Sursă	ad-hoc
Autor	Ciprian Oprisa	Adăugată de	Ciprian Oprisa •cypry
Timp execuţie pe test	0.25 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Subsecvențe tripare

O subsecvenţă a unui şir de numere întregi se numeşte tripară dacă lungimea acesteia este cel puţin trei, iar suma oricăror trei elemente consecutive este pară. De exemplu, în şirul 1, 2, 3, 4, 5, 6, subsecvenţa 1, 3, 4, 5 este tripară, deoarece 1+3+4=8 şi 3+4+5=12, ambele fiind pare. În schimb, subsecvenţa 1, 2, 5, 6 nu este tripară, deoarece 2+5+6=13.

Pentru un şir dat, format din N elemente unice, număraţi câte subsecvenţe tripare conţine. Deoarece acest număr poate fi foarte mare, se va afişa valoarea modulo 666013.

Notă: prin subsecvenţă a unui şir A înţelegem un şir B format din o parte din elementele lui A (sau chiar din toate), aflate în acceeaşi ordine ca şi în A. Elementele din B nu trebuie neapărat să fie pe poziţii consecutive în A. De exemplu, pentru şirul A=[1, 2, 3, 4, 5], subsecvenţele lui de lungime cel puţin 3 sunt [1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4] [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5], [1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 4, 5], [1, 3, 4, 5], [2, 3, 4, 5] şi [1, 2, 3, 4, 5]. Dintre acestea, subsecvenţele [1, 2, 3], [1, 2, 5], [1, 3, 4], [1, 4, 5], [2, 3, 5], [3, 4, 5], [1, 2, 3, 5] şi [1, 3, 4, 5] sunt tripare.

Date de intrare

Fişierul de intrare tripar.in conţine pe prima linie numărul de teste T. Fiecare test va fi format din două linii. Pe prima linie a unui test se va găsi numărul de elemente din şir N. Pe a doua linie a testului se vor găsi N numere întregi pozitive distincte.

Date de ieşire

În fişierul de ieşire tripar.out se va tipări câte o linie pentru fiecare test, conţinând numărul de subsecvenţe tripare ale şirului dat, modulo 666013.

Restricţii

• 1 ≤ N ≤ 100000
• 1 ≤ T ≤ 30

Exemplu

Cum se trimit solutii?