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
102
103
104
105
106
107
// 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i, p, k) for(int i(p); i < k; ++i)
typedef long long int ll;
typedef long double ld;
template <typename T = int> inline T in()
{
    T x;
    std::cin >> x;
    return x;
}
constexpr int mod = 1e9 + 7;
class intm
{
    int val;
    public:
    intm() = default;
    intm(int a) : val{a} {}
    explicit operator int() {return val;}   
    explicit operator long long() {return val;}
    friend intm operator+(intm a, intm b){return ((long long)a + (long long)b) % mod;}
    friend intm operator-(intm a, intm b){return (mod + (long long)a - (long long)b) % mod;}
    friend intm operator*(intm a, intm b){return ((long long)a * (long long)b) % mod;}
    friend intm operator-(intm a){return intm(0) - a;} 
    friend intm operator+(intm a){return a;} 
    friend intm operator!(intm a){return !a.val;} 
    intm operator++ () {return *this = *this+1;}
    intm operator-- () {return *this = *this-1;}
    friend intm operator^(intm a, long long b)
    {
        if(!b)return 1;
        if(b & 1)return a*(a^(b-1));
        intm p(a^(b/2));
        return p*p;
    }
    intm operator+=(intm b){return *this = *this + b;}
    intm operator-=(intm b){return *this = *this - b;}
    intm operator*=(intm b){return *this = *this * b;}
    intm operator^=(long long b){return *this = *this ^ b;}
    friend std::ostream& operator<<(std::ostream& out, intm i){return out << i.val;}
    friend std::istream& operator>>(std::istream& in, intm i){return in >> i.val;}
    friend bool operator==(intm a, intm b){return a.val == b.val;}
    friend bool operator!=(intm a, intm b){return a.val != b.val;}
    friend bool operator<(intm a, intm b){return a.val < b.val;}
    friend bool operator>(intm a, intm b){return a.val > b.val;}
};
class inttree : private std::vector <intm>
{
    int pol;
public:
    inttree(int a)
    {
        for(int s(1); ; s *= 2) if(s > 2*a)
        {
            resize(s);
            break;
        }
        pol = size()/2;
    }
    void add(int g, intm co) 
    {
        g += pol;
        do{
            std::vector<intm>::operator[](g) += co;
            g /= 2;
        } while (g);
    }
    intm operator() (int a, int b) const
    {
        intm wyn(0);
        a += pol - 1;
        b += pol + 1;
        while(a + 1 != b)
        {
            if(!(a & 1))wyn += std::vector<intm>::operator[](a+1);
            if(b & 1)wyn += std::vector<intm>::operator[](b-1);
            a >>= 1;
            b >>= 1;
        }
        return wyn;
    }

};

int main()
{
    std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios_base::sync_with_stdio(0);
    int n(in());
    std::vector <int> tab(n+1);
    rep(i, 1, n+1)std::cin >> tab[i];
    std::vector <std::pair <intm, int>> res{{{0, 0}}, {}};
    intm sum(0);
    rep(i, 1, n+1)
    {
        sum += tab[i];
        res.push_back({sum, i});
    }
    std::sort(res.begin(), res.end());
    std::vector <std::pair <bool, int>>id(n+1); 
    rep(j, 0, n+1)id[res[j].second] = {int(res[j].first) % 2, j};
    inttree odp[2]{n, n};
    odp[0].add(0, 1);
    rep(i, 1, n+1)odp[id[i].first].add(id[i].second, odp[id[i].first](0, id[i].second) + odp[!id[i].first](id[i].second, n));
    std::cout << odp[id[n].first](id[n].second, id[n].second)<<'\n';
    return 0;
}