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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int ps[300300];
int dp[300300];
int M = 1000000007;

int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&ps[i]);
    for (int i=1;i<=n;i++)
    {
        ps[i] += ps[i-1];
        if (ps[i] >= M) ps[i] -= M;
    }

    dp[0]=1;
    int r;
    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<i;j++)
        {
            r = M + ps[i] - ps[j];
            if (r >= M) r-= M;
            if ((r & 1) == 0)
            {
                dp[i] += dp[j];
                if (dp[i] >= M) dp[i] -= M;
            }

        }
    }
    printf("%d\n", dp[n]);
}