DP... dp[k][i][j]: number of subsequences using first k elements, where the last two parities are (i, j), with

include <bits/stdc++.h>

using namespace std;

static const long long MOD = 1000000007;

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

int n;
cin >> n;
vector<long long> a(n);
for(int i = 0; i < n; i++){
    cin >> a[i];
}

// dp[k][i][j]: number of subsequences using first k elements
// where the last two parities are (i, j), with:
// 0 = none, 1 = even, 2 = odd
vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(3, vector<long long>(3, 0)));
dp[0][0][0] = 1; // Base case: empty subsequence

for(int k = 0; k < n; k++){
    int p = (a[k] % 2 == 0 ? 1 : 2);
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            // Case 1: don't take a[k]
            dp[k + 1][i][j] = (dp[k + 1][i][j] + dp[k][i][j]) % MOD;

            // Case 2: take a[k] if it doesn't form 3 same parity
            if (!(i == j && j == p)) {
                dp[k + 1][j][p] = (dp[k + 1][j][p] + dp[k][i][j]) % MOD;
            }
        }
    }
}

// sum over all final dp[n][i][j] and subtract empty subsequence
long long ans = 0;
for(int i = 0; i < 3; i++){
    for(int j = 0; j < 3; j++){
        ans = (ans + dp[n][i][j]) % MOD;
    }
}
ans = (ans - 1 + MOD) % MOD;

cout << ans << "\n";
return 0;

}

Precomputation + Binary Search

include <bits/stdc++.h>

using namespace std;

// Compare numeric strings by length then lex bool numLess(const string &a, const string &b) { if (a.size() != b.size()) return a.size() < b.size(); return a < b; }

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

// 1) Precompute all special palindromes
vector<string> pals;
for(int mask = 1; mask < (1<<9); ++mask){
    // count how many odd digits are selected
    int oddCount = 0, oddDigit = -1;
    for(int d = 1; d <= 9; ++d){
        if (mask & (1<<(d-1))){
            if (d % 2 == 1) {
                oddCount++;
                oddDigit = d;
            }
        }
    }
    if (oddCount > 1) continue;  // can't form palindrome

    // build half-string: for each selected d, add floor(d/2) copies of '0'+d
    string half;
    for(int d = 1; d <= 9; ++d){
        if (mask & (1<<(d-1))){
            half.append(d/2, char('0' + d));
        }
    }
    // build the full palindrome
    string rev = half;
    reverse(rev.begin(), rev.end());
    string pal = half;
    if (oddCount == 1) 
        pal.push_back(char('0' + oddDigit));
    pal += rev;

    pals.push_back(pal);
}

// 2) Sort by numeric value
sort(pals.begin(), pals.end(), numLess);

// 3) Answer queries
int T;
cin >> T;
while(T--){
    string n;
    cin >> n;
    // find first palindrome strictly > n
    auto it = upper_bound(
        pals.begin(), pals.end(), n,
        [](const string &a, const string &b){
            return numLess(a,b);
        }
    );
    // it is guaranteed to exist because the largest precomputed is > 10^17
    cout << *it << "\n";
}
return 0;

}