cs

const int MOD = 1e9 + 7;

bool isValidPartition(const vector<int>& partitionSums) {
    for (int i = 1; i < partitionSums.size(); i++) {
        if (partitionSums[i] % 2 == partitionSums[i - 1] % 2) {
            return false;
        }
    }
    return true;
}

void generatePartitions(int index, const vector<int>& arr, vector<int>& currentPartitionSums, int& count) {
    int n = arr.size();

    if (index == n) {
        if (isValidPartition(currentPartitionSums)) {
            count = (count + 1) % MOD;
        }
        return;
    }

    int sum = 0;
    for (int i = index; i < n; i++) {
        sum += arr[i];
        currentPartitionSums.push_back(sum);
        generatePartitions(i + 1, arr, currentPartitionSums, count);
        currentPartitionSums.pop_back();
    }
}

int countValidPartitions(vector<int>& arr) {
    int count = 0;
    vector<int> currentPartitionSums;

    generatePartitions(0, arr, currentPartitionSums, count);

    return count;
}