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
//Mateusz Piórkowski
#include <iostream>

#define MOD_VAL 1000000007

int n;
uint64_t* numbers;
int64_t* solutions;

uint64_t solve(int pos){
	if(solutions[pos]!=-1){
		return solutions[pos];
	}

	uint64_t current=0;
	uint64_t output=0;
	for(int i=pos; i<n; i++){
		current=(current+numbers[i])%MOD_VAL;
		if((current%2)==0){ //Mopadulo
			if((i+1)>=n){ //End of the numbers array
				output=(output+1)%MOD_VAL;
			}else{
				output=(output+solve(i+1))%MOD_VAL;
			}
		}
	}
	solutions[pos] = output;
	return output;
}

int main(){
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	std::cin >> n;
	numbers = new uint64_t[n];
	for(int i=0; i<n; i++){
		uint64_t num;
		std::cin >> num;
		numbers[i] = num;
	}
	solutions = new int64_t[n];
	for(int i=0; i<n; i++) solutions[i] = -1;
	uint64_t output = solve(0);
	std::cout << output << "\n";
}