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 <unordered_map>
#include <iostream>

constexpr int TWO_20 = 1048576;
constexpr int MAX_N = 300000;
constexpr long long PRIME = 1000000007;
int a[MAX_N];
int n;

std::unordered_map<int, int> fCacheMap;
long long fIterations = 0;
long long gIterations = 0;

long long gCache[TWO_20];


int power2(int p) {
    int result = 1;
    for (int i = 0; i < p; i++) {
        result *= 2;
    }
    return result;
}

long long prepareSegmentTree(int nodeIndex, int rangeStart, int rangeEnd) {
    if (rangeStart == rangeEnd) {
        gCache[nodeIndex] = a[rangeStart];
        return gCache[nodeIndex];
    }

    int rangeMiddle = rangeStart + (rangeEnd - rangeStart) / 2;

    auto value = prepareSegmentTree(2 * nodeIndex + 1, rangeStart, rangeMiddle) + prepareSegmentTree(2 * nodeIndex + 2, rangeMiddle + 1, rangeEnd);
    gCache[nodeIndex] = value % PRIME;
    return gCache[nodeIndex];
}


long long getSum(int nodeIndex, int nodeRangeStart, int nodeRangeEnd, int rangeStart, int rangeEnd)
{
    if (rangeStart <= nodeRangeStart && rangeEnd >= nodeRangeEnd)
        return gCache[nodeIndex];

    if (nodeRangeEnd < rangeStart || nodeRangeStart > rangeEnd)
        return 0;

    int rangeMiddle = nodeRangeStart + (nodeRangeEnd - nodeRangeStart) / 2;
    long long result = getSum(2 * nodeIndex + 1, nodeRangeStart, rangeMiddle, rangeStart, rangeEnd) +
        getSum(2 * nodeIndex + 2, rangeMiddle + 1, nodeRangeEnd, rangeStart, rangeEnd);
    return result % PRIME;
}

void readInput() {
    std::cin >> n;

    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    prepareSegmentTree(0, 0, n - 1);
}

int g(int start, int end) {
    long long result = getSum(0, 0, n - 1, start, end);
    result = result % 2 == 0 ? 1 : 0;
    return result;
}

long long f(int end) {
    if (fCacheMap.find(end) != fCacheMap.end()) {
        return fCacheMap[end];
    }

    long long result = 0;
    int i = 0;
    for (; i < end; i++) {
        long long firstPart = g(i + 1, end);
        if (firstPart == 0)
            continue;
        long long secondPart = f(i);
        if (secondPart == 0)
            continue;
        result += firstPart * secondPart;
        result = result % PRIME;
    }
    fIterations += i;
    result += g(0, end);
    result = result % PRIME;
    fCacheMap[end] = result;
    return result;
}

void solve() {
    readInput();
    auto result = f(n - 1);
    std::cout << result;
}

int main() {
    solve();
    return 0;
}