1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <list>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;

const long P = 1000000007;

long p(long liczba){
	if(liczba==-1) return 0;
	long wynik = (liczba % P) % 2;
	
	if(wynik==0) return 1;
	return 0;
}

long f(const long n, long*tab){
	
	//cout << "1 n="<< n << " "; */for (long i=0; i<n; i++) cout << endl;//cout << tab[i] << " ";	cout << endl;
	//cout << endl;
	long ile=0;
	
	if(n==0) {
//		cout << "n=0; return 0"<< endl;
		return 0;	
	}
	
	if(tab[0]==-1) {
//		cout << "tab[0]==-1 return f(tab+1)" << endl;
		return f(n-1, tab+1);	
	}
		
	if(n==1) {
//		cout << "n=1, return "<< p(tab[0])<< endl;
		return p(tab[0]);	
	}
	long i, suma=0;

			
	ile+=( p(tab[0]) * f(n-1, tab+1) ) %P;
//	cout << "2 n="<< n << " "; for (int i=0; i<n; i++) cout << tab[i] << " ";	cout << endl;
//	cout << "ile1: " << ile << endl;
	
	for (i=0; i< n; i++){ 
		if(tab[i]!=-1)
			suma+=tab[i];
	}
	ile+=p(suma) % P;
//	cout << "3 n="<< n << " "; for (int i=0; i<n; i++) cout << tab[i] << " ";	cout << endl;
//	cout << "ile2: " << ile << ", suma: "<<suma<<endl;
	
	for (i=1; i< n; i++){
		if ( tab[i] != -1 && p(tab[0]+tab[i]) ){
			long pom = tab[i];
			
//			cout <<endl;
			tab[i]=-1;				// specjalna wartosc, oznacza, ze tego nie ma
			ile += f(n-1, tab+1) %P;
			tab[i] = pom;
		}
	}

//	cout << "4 n="<< n << " "; for (int i=0; i<n; i++) cout << tab[i] << " ";	cout << "ile3: " << ile << endl;
	return ile %P;
}

int main(int argc, char** argv) {
	
	long n, i;
	long tab[300001];
	cin >> n;
	for(i=0; i<n; i++)
		cin >> tab[i];

//	cout << "wynik: "<< f(n, tab) << endl;	
	cout << f(n, tab) << endl;	
	return 0;
}