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
79
80
81
//runda 3B
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
long long a, wynik = 0LL, pierwsza = 1000000007LL;
vector<long> wejscie;


void Przedzialy(int start, int end, int ilosc) {
	long long sumaP = 0LL, sumaK = 0LL;

	if(end - start + 1 < ilosc)
		return;
	if(ilosc == 1) {
		for(int i = start; i <= end; ++i) {
			sumaK += wejscie[i];
			sumaK = sumaK % pierwsza;
		}
		if(!(sumaK % 2)) {
			++wynik;
			wynik = wynik % pierwsza;
		}
		//cout << start << " - " << end << " - " << ilosc << endl;
		return;
	}
	if(ilosc == 2) {
		for(int i = start; i <= end; ++i) {
			sumaK += wejscie[i];
			sumaK = sumaK % pierwsza;
		}
		for(int i = start; i < end; ++i) {
			sumaP += wejscie[i];
			sumaP = sumaP % pierwsza;
			sumaK += pierwsza;
			sumaK -= wejscie[i];
			sumaK = sumaK % pierwsza;
			if(!(sumaK % 2) && !(sumaP % 2)) {
				++wynik;
				wynik = wynik % pierwsza;
			}
		//	cout << start << " - " << i << " # " << i + 1 << " - " << end << " # " << ilosc << endl;
		}
		return;
	}
	//cout << start <<"tu" << endl;
	for(int i = start; i <= end - ilosc + 1; ++i) {
		//cout << i << " - " << end - (start + ilosc - i) - 1 << " - " << ilosc << endl;
		sumaP += wejscie[i];
		sumaP = sumaP % pierwsza;
		sumaK = 0LL;
		for(int j = end; j >= i + ilosc - 1; --j) {
			//cout << start << " - " << i << " # " << j << " - " << end << " # " << ilosc << endl;
			sumaK += wejscie[j];
			sumaK = sumaK % pierwsza;
			if(!(sumaK % 2) && !(sumaP % 2))
				Przedzialy(i + 1, j - 1, ilosc - 2);
		}
	}
}

int main() {
  ios_base::sync_with_stdio(0);

  cin >> n;
  for(int iN = 0; iN < n; ++iN) {
	  cin >> a;
	  wejscie.push_back(a);
  }

  for(int iP = 1; iP <= n; ++iP)
	  Przedzialy(0, n - 1 , iP);

  //Przedzialy(0, n - 1 , 200);

  cout << wynik;
  return 0;
}