Untitled

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


using ll = long long;
const int MOD = 1e9 + 7;

int mul(ll a, ll b){
  return (a%MOD)*(b%MOD) % MOD;
}
int add(ll a, ll b){
  return (a+b) % MOD;
}
int sub(ll a, ll b){
  return (a-b+2*MOD) % MOD;
}
int fastPow(ll a, ll b){
  ll res = 1;
  while(b){
    if(b&1) res = mul(res, a);
    b >>= 1;
    a = mul(a, a);
  }
  return res;
}

class Solution {
public:
    int countStableSubsequences(vector<int>& nums) {
      int n = nums.size();
      int ans = fastPow(2, n);
      vector<int> sufodd(n+1),  sufeven(n+1), oddcnt(n+1), evencnt(n+1), preodd(n+1), preeven(n+1);
      for(int i = n-1; i >= 0; --i){
          sufodd[i] = sufodd[i+1];
          sufeven[i] = sufeven[i+1];
          if(nums[i]&1) sufodd[i] = add(sufodd[i], fastPow(2, n-1-i));
          else sufeven[i] = add(sufeven[i], fastPow(2, n-1-i));
      }
      for(int i = 0; i < n; ++i){
        oddcnt[i] = (i ? oddcnt[i-1] : 0) + (nums[i]&1);
        evencnt[i] = (i ? evencnt[i-1] : 0) + (!(nums[i]&1));
        
        preodd[i] = (i ? preodd[i-1] : 0);
        preeven[i] = (i ? preeven[i-1] : 0);
        if(nums[i]&1)  preodd[i] = add(preodd[i], fastPow(2, i));
        else preeven[i] = add(preeven[i], fastPow(2, i));
      }
      // sufodd -> number of subseq starting from i and first element is odd
      
      // even  2^i * (1 + sufodd[i]) * (evencntsuf[pos + 2] - evencntsuf[i])
      for(int i = n-1; i >= 0; --i){
        if(nums[i]&1) continue;
        int l = 0, r = i-1, pos = -1;
        while(l <= r){
          int mid = (l+r) >> 1;
          int cnt = evencnt[i] - evencnt[mid] + (!(nums[mid]&1));
          if(cnt >= 3) pos = mid, l = mid + 1;
          else r = mid - 1;
        }
        if(pos == -1) break;
        cout << pos << " " << i << " " << preeven[pos] << " " << sufodd[i] + 1 << '\n';
      }
      return 0;
    }
};

int32_t main(){
   Solution s{};
   vector<int> nums{3, 4, 1, 2, 8, 6, 9};
   cout << s.countStableSubsequences(nums);
}