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}
.