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
#include<bits/stdc++.h>
using namespace std;
constexpr long long mod = 1000000007;
long long tree[2][1 << 20], dp;
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int n = 0;
  cin >> n;
  
  vector<long long> pref(n + 1, 0ll);
  set<long long> pref_sum_map;
  for(int i = 1;i <= n;i++){
    cin >> dp;
    pref[i] = (pref[i - 1] + dp) % mod;
    pref_sum_map.emplace(pref[i]);
  }
  
  int M = 1, map_cnt = 0; while(M <= n) M <<= 1;
  map<long long, int> mapped_pref;
  for(auto i : pref_sum_map) mapped_pref[i] = ++map_cnt;
  
  auto update = [&](const int type, int v, long long x){
    for(v += M - 1;v;v >>= 1) tree[type][v] = (tree[type][v] + x) % mod;
  };

  auto query = [&](const int type, int p, int k, long long res = 0){
    for(p += M - 1, k += M - 1;p <= k && p && k;p >>= 1, k >>= 1){
      if(p % 2 == 1) res = (res + tree[type][p++]) % mod;
      if(k % 2 == 0) res = (res + tree[type][k--]) % mod;
    }
    return res;
  };

  update(0, 1, 1);
  for(int i = 1;i <= n;i++){
    int type = pref[i] & 1ll, v = mapped_pref[pref[i]];
    dp = (query(type, 1, v) + query(type ^ 1, v + 1, map_cnt)) % mod;
    update(type, v, dp);
  }

  cout << dp << '\n';
}