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
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define UI unsigned int

const UI t = 3e5 + 9, p = 1e9 + 7, siz = 2147483648;
LL tab[t], dp[t];

struct Vertex {
    UI left, right;
    UI sp = 0, sn = 0;
    Vertex *left_child = nullptr, *right_child = nullptr;
    Vertex(UI lb, UI rb) {
        left = lb;
        right = rb;
    }
    void extend() {
        if(!left_child && left + 1 < right) {
            UI t = (left + right) / 2;
            left_child = new Vertex(left, t);
            right_child = new Vertex(t, right);
        }
    }
    void add(UI k, UI x) {
        if(left + 1 == right) {
            if(left % 2) sp = (sp + x) % p;
            else sn = (sn + x) % p;
        }
        else {
            extend();
            if (left_child) {
                if (k < left_child->right)
                    left_child->add(k, x);
                else
                    right_child->add(k, x);
            }
            sp = (left_child->sp + right_child->sp) % p;
            sn = (left_child->sn + right_child->sn) % p;
        }
    }
    LL get_sum(UI lq, UI rq, int x) {
        if(lq <= left && right <= rq) {
            if(x == 0) return sp;
            else return sn;
        }
        if(max(left, lq) >= min(right, rq)) return 0;
        extend();
        return(left_child->get_sum(lq, rq, x) + right_child->get_sum(lq, rq, x)) % p;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    if(n > 3000) {
        Vertex root(0, siz);
        root.add(0, 1);
        tab[0] = 0;
        for(int i = 1; i <= n; i ++) {
            LL x;
            cin >> x;
            tab[i] = tab[i - 1] + x;
        }
        dp[0] = 1;
        for(int i = 1; i <= n; i ++) {
            LL l, r;
            l = 1 + ((LL) p + 1) * (tab[i] % (2 * p));
            l = l % (2 * p);
            r = l + p - 1;
            dp[i] += root.get_sum(l, min(r + 1, (LL) 2 * p), 0);
            if(r >= 2 * p) dp[i] += root.get_sum(0, r % (2 * p) + 1, 0);
            l = p + 1 + ((LL) p + 1) * (tab[i] % (2 * p));
            l = l % (2 * p);
            r = l + p - 1;
            dp[i] += root.get_sum(l, min(r + 1, (LL) 2 * p), 1);
            if(r >= 2 * p) dp[i] += root.get_sum(0, r % (2 * p) + 1, 1);
            dp[i] = dp[i] % p;
            root.add(tab[i] % (2 * p), dp[i]);
        }
        cout << dp[n];
    }
    else {
        tab[0] = 0;
        for(int i = 1; i <= n; i ++) {
            LL x;
            cin >> x;
            tab[i] = tab[i - 1] + x;
        }
        dp[0] = 1;
        for(int i = 1; i <= n; i ++) {
            for(int k = 0; k < i; k ++) {
                if(((tab[i] - tab[k]) % p) % 2 == 0) dp[i] = (dp[i] + dp[k]) % p;
            }
        }
        cout << dp[n];
    }
    return 0;
}