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

#include <bits/stdc++.h>

using namespace std;

int n , cnt , x;
#define MOD 666013
ifstream cin("memory005.in");
ofstream cout("memory005.out");
int put(int n)
{
    int p = 1;
    for(int i = 1 ; i <= n ; i++)
        p *= 2 , p %= MOD;
    return p;
}
int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> x;
        if(x % 2 == 1) cnt++;
    }
    if(cnt == 0) cout << (put(n) - 1) % MOD;
    else cout << (put(n - 1) - 1) % MOD;
    return 0;
}