Cerința

Se dă o mulţime A formată din n elemente, numere naturale ( evident distincte ). Aflaţi câte submulţimi nevide ale lui A au suma elementelor număr par.

Date de intrare

Fișierul de intrare memory005.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale distincte, separate prin spații, reprezentând elementele mulţimii A.

Date de ieșire

Fișierul de ieșire memory005.out va conține pe prima linie numărul S, reprezentând numărul submulţimilor nevide ale lui A care au suma elementelor număr par. Rezultatul se va afişa modulo 666013.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000
• numerele de pe a doua linie a fișierului de intrare vor fi distincte şi mai mici decât 2.000.000.000

Exemplu:

memory005.in

4
1 3 8 2

memory005.out

7

Explicație

Avem mulţimea A={1,3,8,2}. Submulţimile nevide ale lui A având suma elementelor număr par sunt: {8}, {2}, {1,3}, {8,2}, {1,3,8}, {1,3,2}, {1,3,8,2}.