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

%!{float: right; height: 450px} problema/azerah?por_costel_azerah.jpg!%

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:

Por Costel a primit o invitaţie regală la palatul împăratului ouşor al programării, Azerah. Azerah a auzit de vestitul porc şi a vrut să îl vadă cu ochii săi. Por Costel, ajuns la palat, îi spune împăratului ouşor că “pare bun de mâncat”. Azerah se simte insultat (deşi Por Costel o spusese ca pe un compliment) şi, înfuriat până la gălbenuş, îl ameninţă pe prietenul nostru cu moartea dacă acesta nu îi va aduce soluţia la o problemă de numărare care îl măcina de ceva vreme:

Dandu-se un sir de numere, cate subsiruri (submultimi) au suma numerelor para ?

Dându-se un şir de numere, câte subşiruri (submulţimi nevide) au suma numerelor pară ?
 
Ajutaţi-l pe Por Costel să scape şi din aceasta năzbâtie !

Ajutati-l pe Por Costel sa scape si din aceasta nazbatie !

h2. Date de intrare

Fişierul de intrare $azerah.in$ va conţine pe prima linie <tex>T</tex>, numărul de teste. Un test are următorul format: pe prima linie <tex>N</tex> (numărul de numere) iar apoi pe următoarea linie se vor afla cele <tex>N</tex> numere.

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

h2. Date de ieşire

În fişierul de ieşire $azerah.out$ se vor afla <tex>T</tex> linii, pe linia <tex>i</tex> se află răspunsul la întrebarea <tex>i</tex>. Afişati rezultatul modulo <tex>10^9 + 7</tex> (Azerah oricum nu-şi va da seama).

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

h2. Restricţii
* <tex>1</tex> &le; suma tuturor <tex>N</tex>-urilor &le; <tex>10^6</tex>

* <tex>1</tex> &le; fiecare număr din şir &le; <tex>10^9</tex>

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

h2. Exemplu

10325