azerah

Por Costel si Azerah

== include(page="template/taskheader" task_id="azerah") ==

Poveste şi cerinţă...

Por Costel a primit o invitatie regala la palatul imparatului ousor al programarii, Azerah. Azerah a auzit de vestitul porc si a vrut sa il vada cu ochii sai. Por Costel, ajuns la palat, ii spune imparatului ousor ca “pare bun de mancare”. Azerah se simte insultat (desi Por Costel o spusese ca un compliment) si, infuriat pana la galbenus, il ameninta pe prietenul nostru cu moartea daca acesta nu ii va aduce solutia la o problema de numarare care il macina de ceva vreme:
 
Dandu-se un sir de numere, cate subsiruri (submultimi) au suma numerelor para ?
 
Ajutati-l pe Por Costel sa scape si din aceasta nazbatie !
 

h2. Date de intrare

Fişierul de intrare $azerah.in$ ...

Fişierul de intrare $azerah.in$ va contine pe prima linie T, numarul de teste. Un test are urmatorul format: pe prima linie N (numarul de numere) iar apoi pe urmatoarea linie se vor afla cele N numere.

h2. Date de ieşire

În fişierul de ieşire $azerah.out$ ...

În fişierul de ieşire $azerah.out$ se vor afla T linii, pe linia i se afla raspunsul la intrebarea i. Afisati-l modulo 10^9 + 7 (Azerah oricum nu-si va da seama).

h2. Restricţii

* $... ≤ ... ≤ ...$

* <tex>1</tex> &le; <tex>N</tex> &le; <tex>10^6</tex>
* <tex>1</tex> &le; fiecare numar din sir &le; <tex>10^9</tex>

h2. Exemplu