solve the question in C++

Idea & Approach

Only the parity of every element matters, because the rule is about consecutive evens or odds.
While we scan the array we maintain how many valid subsequences end with the last 1 or 2 elements being even/odd:

state	meaning
E1	ends in one even (… odd , even)
E2	ends in two evens (… odd , even, even)
O1	ends in one odd (… even , odd)
O2	ends in two odds (… even , odd, odd)

A third same-parity element would violate the rule, so we never create such a state.

Processing an element x:

If x is even

text
newE1 = 1                         // subseq consisting of only x
       + O1 + O2                  // append x after an odd run
newE2 = E1                        // append x after a single even
// sequences that ignore x keep their old states
E1 = (E1 + newE1) mod M
E2 = (E2 + newE2) mod M

If x is odd – symmetric with the roles of even/odd swapped.

At each step we keep everything mod M = 1 000 000 007.
After the whole array the answer is

(E1 + E2 + O1 + O2) mod M

because every non-empty valid subsequence ends in exactly one of the four states.

The algorithm is O(N) per test case and O(1) extra memory.

---

Reference implementation (C++17)

cpp
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1'000'000'007LL;

int solve(int N, const vector<int>& A) {
    long long E1 = 0, E2 = 0, O1 = 0, O2 = 0;

    for (int x : A) {
        if (x & 1) {                       // x is odd
            long long newO1 = (1 + E1 + E2) % MOD;
            long long newO2 = E1 ? 0 : 0;  // will be set below
            newO2 = O1;                    // append odd after single odd

            O1 = (O1 + newO1) % MOD;
            O2 = (O2 + newO2) % MOD;
        } else {                           // x is even
            long long newE1 = (1 + O1 + O2) % MOD;
            long long newE2 = E1;          // append even after single even

            E1 = (E1 + newE1) % MOD;
            E2 = (E2 + newE2) % MOD;
        }
    }

    return int((E1 + E2 + O1 + O2) % MOD);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;  cin >> T;
    while (T--) {
        int N; cin >> N;
        vector<int> A(N);
        for (int &x : A) cin >> x;
        cout << solve(N, A) << '\n';
    }
    return 0;
}

Why it works

• Every subsequence is built exactly once (the moment we read its last element).
• No subsequence with a run of 3 same-parity numbers is ever generated, because we never allow a transition from E2 → E3 or O2 → O3.
• Modulo arithmetic keeps numbers in range.

This passes the sample cases ([2,2,2] → 6, [1,2,3,5] → 14) and runs easily within the given bounds (N ≤ 10^5, T ≤ 10).