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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <cstdio>

static const int M = 1000000007;

struct node
{
    int c; // liczba ciągów
    node *l, *r; // lewy i prawy syn
};

struct tree
{
    int max; // zakres
    node *root; // korzeń
};

node* __create(int min, int max, int s, int c)
{
    node* root = new node({c, nullptr, nullptr});
    
    if (max - min != 1)
    {
        int med = (min + max) / 2;
        
        if (s < med)
            root->l = __create(min, med, s, c);
        else
            root->r = __create(med, max, s, c);
    }
    
    return root;
}

void __insert(node* root, int min, int max, int s, int c)
{
    root-> c = (root->c + c) % M;
    
    if (max - min != 1)
    {
        int med = (min + max) / 2;
        
        if (s < med)
        {
            if (root->l != nullptr)
                __insert(root->l, min, med, s, c);
            else
                root->l = __create(min, med, s, c);
        }
        else
        {
            if (root->r != nullptr)
                __insert(root->r, med, max, s, c);
            else
                root->r = __create(med, max, s, c);
        }
    }
}

int __read_leq(node* root, int min, int max, int s)
{
    if (root == nullptr)
        return 0;
    
    if (max - min == 1)
        return root->c;
    
    int med = (min + max) / 2;
    
    if (s < med)
        return __read_leq(root->l, min, med, s);
    else
        return ((root->l == nullptr ? 0 : root->l->c) + __read_leq(root->r, med, max, s)) % M;
}

int __read_geq(node* root, int min, int max, int s)
{
    if (root == nullptr)
        return 0;
    
    if (max - min == 1)
        return root->c;
    
    int med = (min + max) / 2;
    
    if (s < med)
        return (__read_geq(root->l, min, med, s) + (root->r == nullptr ? 0 : root->r->c)) % M;
    else
        return __read_geq(root->r, med, max, s);
}

void insert(tree* t, int s, int c)
{
    if (t->root == nullptr)
    {
        while (t->max <= s)
            t->max *= 2;
        t->root = __create(0, t->max, s, c);
    }
    else
    {
        while (t->max <= s)
        {
            t->max *= 2;
            t->root = new node({t->root->c, t->root, nullptr});
        }
        
        __insert(t->root, 0, t->max, s, c);
    }
}

int read_leq(tree* t, int s)
{
    return __read_leq(t->root, 0, t->max, s);
}

int read_geq(tree* t, int s)
{
    return __read_geq(t->root, 0, t->max, s);
}

int main()
{
    tree parzyste = { 1, nullptr };
    tree nieparzyste = { 1, nullptr };
    
    int n;
    scanf("%d", &n);
    
    int x, s = 0, c;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &x);
        s = (s + x) % M;
        if (s % 2 == 0)
        {
            c = (read_leq(&parzyste, s) + read_geq(&nieparzyste, s) + 1) % M;
            insert(&parzyste, s, c);
        }
        else
        {
            c = (read_leq(&nieparzyste, s) + read_geq(&parzyste, s)) % M;
            insert(&nieparzyste, s, c);
        }
    }
    
    printf("%d\n", c);
    
    return 0;
}