dqasd

const int MOD = 1e9 + 7;
int generatePartitions(int index, const vector<int>& arr, int lastSumParity, vector<vector<int>>& dp) {
    int n = arr.size();
    if (index == n) return 1;

    if (dp[index][lastSumParity + 1] != -1) return dp[index][lastSumParity + 1];

    int sum = 0;
    int count = 0;

    for (int i = index; i < n; i++) {
        sum += arr[i];
        int currentSumParity = sum % 2;
        if (lastSumParity == -1 || currentSumParity != lastSumParity) {
            count = (count + generatePartitions(i + 1, arr, currentSumParity, dp)) % MOD;
        }
    }
    return dp[index][lastSumParity + 1] = count;
}

int countValidPartitions(const vector<int>& arr) {
    int n = arr.size();
    vector<vector<int>> dp(n, vector<int>(3, -1));
    return generatePartitions(0, arr, -1, dp);
}