#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

vector<int> calculatePrefixSums(const vector<int>& arr) {
    int n = arr.size();
    vector<int> prefixSums(n);
    prefixSums[0] = arr[0];
    for (int i = 1; i < n; ++i) {
        prefixSums[i] = prefixSums[i - 1] + arr[i];
    }
    return prefixSums;
}

int countValidPartitions(const vector<int>& arr) {
    int n = arr.size();

    if (n == 0) return 0;

    vector<int> prefixSums = calculatePrefixSums(arr);

    vector<vector<int>> dp(n + 1, vector<int>(2, 0));

    dp[n][0] = dp[n][1] = 1;

    for (int i = n - 1; i >= 0; --i) {
        int sum = 0;
        for (int j = i; j < n; ++j) {
            sum = prefixSums[j] - (i > 0 ? prefixSums[i - 1] : 0);
            int currentSumParity = sum % 2;

            if (currentSumParity == 0) {
                dp[i][0] = (dp[i][0] + dp[j + 1][1]) % MOD;
            } else {
                dp[i][1] = (dp[i][1] + dp[j + 1][0]) % MOD;
            }
        }
    }
    return (dp[0][0] + dp[0][1]) % MOD;
}

int main() {
    // Input example
    int n = 4;
    vector<int> arr = {1, 1, 1, 1};  // Example array

    cout << "Number of valid partitions (Optimized): " << countValidPartitions(arr) << endl;

    return 0;
}