Subsequences with a unique middle mode i

impl Solution {
  pub fn subsequences_with_middle_mode(nums: Vec<i32>) -> i32 {
    // For each position m as the "middle" of a size-5 subsequence:
    //   v = nums[m], lv = count of v to the left, rv = count of v to the right
    //   ll = m (total positions left), rr = n-m-1 (total positions right)
    //   nl = ll - lv (non-v left count), nr = rr - rv (non-v right count)
    //
    // We choose 2 from left and 2 from right. Let vl (resp vr) = # of v chosen from left (right).
    // vl in 0..=min(lv,2), vr in 0..=min(rv,2), and we choose (2-vl) non-v from left, (2-vr) from right.
    //
    // A subsequence is valid (v is unique mode) iff freq(v) > freq(any other value).
    // Total freq(v) = 1 + vl + vr.
    //
    // Case vl+vr >= 2 (freq(v) >= 3): any other value appears at most 2 < 3 → always valid.
    // Case vl+vr == 1 (freq(v) == 2): valid iff no non-v value appears >= 2 times
    //   i.e., the 3 non-v elements chosen are all distinct values.
    // Case vl+vr == 0 (freq(v) == 1): NOT valid (4 non-v elements can't all be distinct
    //   in a way that none appears >= 1 = freq(v)... actually valid iff all 4 non-v distinct,
    //   but then freq(v)=1=max and v is unique mode. However freq=1 for all, so v IS the mode
    //   only if all others appear <= 1 time. With 4 elements all distinct, everyone has freq=1
    //   including v, so v is NOT the unique mode (tied). So vl+vr=0 → never valid.
    
    let n = nums.len();
    let md = 1_000_000_007i64;
    let inv2 = 500_000_004i64;
    
    let c2 = |x: i64| -> i64 {
      if x < 2 { 0 } else { x % md * ((x - 1) % md) % md * inv2 % md }
    };
    let c_k = |x: i64, k: i64| -> i64 {
      if k < 0 || x < k { return 0; }
      match k {
        0 => 1,
        1 => x % md,
        2 => { if x < 2 { 0 } else { x % md * ((x-1) % md) % md * inv2 % md } }
        _ => 0,
      }
    };

    use std::collections::HashMap;
    let mut left_cnt: HashMap<i32, i64> = HashMap::new();
    let mut right_cnt: HashMap<i32, i64> = HashMap::new();
    for &x in &nums {
      *right_cnt.entry(x).or_insert(0) += 1;
    }

    let mut ans = 0i64;

    for m in 0..n {
      let v = nums[m];
      // Move v from right to current (middle)
      *right_cnt.get_mut(&v).unwrap() -= 1;

      let lv = *left_cnt.get(&v).unwrap_or(&0);
      let rv = *right_cnt.get(&v).unwrap_or(&0);
      let ll = m as i64;
      let rr = (n - m - 1) as i64;
      let nl = ll - lv;
      let nr = rr - rv;

      // Sum for vl+vr >= 2: always valid
      let mut ways_ge2 = 0i64;
      for vl in 0i64..=lv.min(2) {
        for vr in 0i64..=rv.min(2) {
          if vl + vr < 2 { continue; }
          let left_nv = 2 - vl;
          let right_nv = 2 - vr;
          let w = c_k(lv, vl) * c_k(rv, vr) % md
               * c_k(nl, left_nv) % md
               * c_k(nr, right_nv) % md;
          ways_ge2 = (ways_ge2 + w) % md;
        }
      }

      // Sum for vl+vr == 1: valid iff 3 non-v chosen are all distinct values
      // Case A: vl=1, vr=0 → choose 1 non-v from left, 2 non-v from right, all distinct in values
      // Case B: vl=0, vr=1 → choose 2 non-v from left, 1 non-v from right, all distinct
      
      // For case A: ways = lv * (# pairs: 1 from nl, 2-unordered from nr, all 3 distinct)
      // = lv * [nl*C(nr,2) - sum_{u≠v} lu * C(ru,2)   (pairs with same value on right)
      //                    - sum_{u≠v} lu * ru * (nr - ru)  ... NO
      // 
      // Actually: # (a, {b,c}) with a in left-nonv, {b,c} ⊆ right-nonv, all 3 from distinct values
      // = nl*C(nr,2) - # where b=c (both right same value) - # where a=b or a=c (but b≠c)
      // Wait, "distinct values" means val(a)≠val(b), val(a)≠val(c), val(b)≠val(c).
      // Bad events: val(b)=val(c) OR val(a)=val(b) OR val(a)=val(c).
      // These overlap. Let's use inclusion-exclusion:
      // |A or B or C| = |val(b)=val(c)| + |val(a)=val(b)| + |val(a)=val(c)| - ... (triples overlap)
      // 
      // |val(b)=val(c)|: sum_{u≠v} C(ru,2) * nl = sc2r * nl
      // |val(a)=val(b)| (unordered pair, so val(a) matches one of {b,c}):
      //   = sum_{u≠v} lu * ru * (nr - 1)  ... NO, we're choosing unordered {b,c}
      //   If val(a)=u and one of {b,c}=u: choose a=u (lu ways), choose one of right pair as u (ru ways), choose other right nonv (nr-1 ways). But this counts ordered pairs. For unordered: divide by... no.
      //   Better: # (a, {b,c}): val(a)=u, u ∈ {b,c}, b≠c.
      //   = sum_u lu * [ru * (nr - ru)] (choose a=u: lu ways; choose one right as u: ru ways; choose other right nonv ≠ u: nr-ru ways)
      //   But this overcounts: if both b=u (then val(b)=u=val(a) AND b=c is handled separately)
      //   Actually the set {b,c} must have at least one element = u. Let val(b)=u OR val(c)=u (unordered).
      //   = sum_u lu * [C(ru,1)*(nr-ru) + C(ru,2)] -- wait this mixes two bad events.
      //
      // This inclusion-exclusion is getting complicated. Let me try a direct formula:
      // # valid = # (a, {b,c}): a from left-nonv, {b,c} from right-nonv, all 3 values distinct
      // = C(nl,1)*C(nr,2) - [# where a's value in right pair's values]
      //                   - [# where right pair has same value]
      //                   + [# where a's value in right pair AND right pair same value]
      //   The last term: a=u, b=c=u → lu * C(ru,2). Sum = sum_u lu*C(ru,2) = SumLuC2Ru.
      //   Middle term 2: sum_u C(ru,2) * nl = sc2r_total * nl... NO, nl is total not per-u.
      //   
      // Actually let me just define SumCross = sum_{u≠v} lu*ru.
      // 
      // # valid_A = nl * C(nr,2) 
      //           - sum_u lu * C(ru,1) * (nr - ru)   [a=u, one right = u, other right ≠ u]  
      //           - sum_u lu * C(ru,2)               [a=u, both right = u]
      //           - sum_u C(ru,2) * (nl - lu)         [right pair same value u, a ≠ u]
      //   Hmm (last two combine as sc2r*nl).
      // 
      // Let me try differently: 
      // # valid_A = nl*C(nr,2) - [# where right pair NOT all distinct (same value)]
      //                        - [# where a's value appears in right pair (a=u, one or both of {b,c}=u)]
      //           + [# where both: right pair same value AND a=same u]
      //         = nl*C(nr,2) - sc2r * nl - sum_u lu * (C(ru,1)*(nr-ru) + C(ru,2)) + sum_u lu*C(ru,2)
      //         Wait: sum_u lu * C(ru,1)*(nr-ru) counts (a=u, one right=u, other right≠u).
      //               sum_u lu * C(ru,2) counts (a=u, both right=u).
      //               Total a=u appearing in right: sum_u lu * (ru*(nr-ru) + C(ru,2))
      //                                           = sum_u lu * (ru*(nr-ru) + ru*(ru-1)/2)
      //                                           = sum_u lu * ru * (nr - ru + (ru-1)/2)...
      //             This gets messy with integer division.
      //
      // Cleaner: # valid_A = (total) - (bad where same value appears twice or more)
      // Among (a, b, c) where a∈left_nonv[position], b∈right_nonv[pos], c∈right_nonv[pos], b<c (positions):
      // bad event: val(a)=val(b) OR val(a)=val(c) OR val(b)=val(c)
      // = sum_u [lu * (ru choose 1) * (nr - 1) - ...] 
      //
      // I'll just compute it as: 
      // # where val(b)=val(c): nl * sum_u C(ru,2) = nl * sc2r
      // # where val(a)=val(b) AND val(b)!=val(c): sum_u lu*ru*(nr-ru)
      // # where val(a)=val(c) AND val(c)!=val(b): same = sum_u lu*ru*(nr-ru) [by symmetry]
      // # where val(a)=val(b)=val(c): sum_u lu*C(ru,2)
      // 
      // These are disjoint events (a's value matches left, or right pair same, or mixed).
      // Wait they're NOT disjoint:
      //   val(a)=val(b) AND val(b)=val(c) IS possible (val(a)=val(b)=val(c)).
      //   This is covered in "val(a)=val(b) AND val(b)!=val(c)" + "val(a)=val(b)=val(c)".
      // Let me define:
      //   E1 = val(b)=val(c) [right pair same value]
      //   E2 = val(a) equals any of {val(b), val(c)} [left value in right pair]
      // 
      // # bad = |E1 ∪ E2| = |E1| + |E2| - |E1 ∩ E2|
      // |E1| = nl * sc2r  (for any a in left_nonv, right pair same value)
      // |E2| = sum_u lu * (# pairs {b,c} where u ∈ {val(b),val(c)})
      //      = sum_u lu * [ru*(nr-ru) + C(ru,2)] = sum_u lu * [ru*nr - ru^2 + C(ru,2)]
      //      Hmm: ru*(nr-ru) = # pairs where exactly one b or c = u; C(ru,2) = both are u.
      //      So sum_u lu * [ru*(nr-ru) + C(ru,2)] counts pairs with at least one = u.
      //      = sum_u lu * [nr*ru - C(ru,2) - ... ] 
      //        Actually # pairs from nr items with at least one = u = C(nr,2) - C(nr-ru,2)
      //        = C(nr,2) - C(nr-ru,2).
      //      |E2| = sum_u lu * [C(nr,2) - C(nr-ru, 2)]
      // |E1 ∩ E2| = sum_u lu * C(ru,2)  (right pair same u, left = u)
      //
      // # valid_A = nl*C(nr,2) - nl*sc2r - sum_u lu*[C(nr,2)-C(nr-ru,2)] + sum_u lu*C(ru,2)
      //
      // This is O(n^2) total since we iterate over all unique u values at each middle m.
      // 
      // For simplicity, precompute at each m:
      //   sc2r = sum_u C(ru,2)
      //   sc2l = sum_u C(lu,2)
      //   sum_lu_c2_nr_minus_ru = sum_u lu * C(nr-ru, 2)  -- HARD to compute without iterating
      //
      // Given n ≤ 1000, O(n^2) is fine. Just iterate over all u at each m.

      let all_vals: std::collections::HashSet<i32> =
        left_cnt.keys().chain(right_cnt.keys()).cloned().collect();
      
      let mut sc2l = 0i64;
      let mut sc2r = 0i64;
      let mut sum_lu_c2_nr_ru = 0i64; // sum_u lu * C(nr-ru, 2)
      let mut sum_rv_c2_nl_lu = 0i64; // sum_u ru * C(nl-lu, 2)
      let mut sum_lu_c2_ru = 0i64;    // sum_u lu * C(ru, 2)
      let mut sum_ru_c2_lu = 0i64;    // sum_u ru * C(lu, 2)

      for u in &all_vals {
        if *u == v { continue; }
        let lu = *left_cnt.get(u).unwrap_or(&0);
        let ru = *right_cnt.get(u).unwrap_or(&0);
        sc2l = (sc2l + c2(lu)) % md;
        sc2r = (sc2r + c2(ru)) % md;
        sum_lu_c2_nr_ru = (sum_lu_c2_nr_ru + lu % md * c2(nr - ru) % md) % md;
        sum_rv_c2_nl_lu = (sum_rv_c2_nl_lu + ru % md * c2(nl - lu) % md) % md;
        sum_lu_c2_ru = (sum_lu_c2_ru + lu % md * c2(ru) % md) % md;
        sum_ru_c2_lu = (sum_ru_c2_lu + ru % md * c2(lu) % md) % md;
      }

      // Case A: vl=1, vr=0. ways = lv * valid_A
      // valid_A = nl*C(nr,2) - nl*sc2r - sum_u lu*[C(nr,2)-C(nr-ru,2)] + sum_u lu*C(ru,2)
      //         = nl*C(nr,2) - nl*sc2r - sum_u lu*C(nr,2) + sum_lu_c2_nr_ru + sum_lu_c2_ru
      //         = (nl - sum_lu)*C(nr,2) - nl*sc2r + sum_lu_c2_nr_ru + sum_lu_c2_ru
      //   wait: sum_u lu = nl. And sum_u lu * C(nr,2) = nl * C(nr,2).
      //         = nl*C(nr,2) - nl*sc2r - nl*C(nr,2) + sum_lu_c2_nr_ru + sum_lu_c2_ru
      //         = -nl*sc2r + sum_lu_c2_nr_ru + sum_lu_c2_ru
      let c_nr_2 = c2(nr);
      let c_nl_2 = c2(nl);
      let valid_a = (md + md - nl % md * sc2r % md % md + sum_lu_c2_nr_ru + sum_lu_c2_ru) % md;
      let ways_v1_a = lv % md * valid_a % md;

      // Case B: vl=0, vr=1. ways = rv * valid_B (symmetric)
      // valid_B = nr*C(nl,2) - nr*sc2l - nr*C(nl,2) + sum_ru_c2_nl_lu + sum_ru_c2_lu
      //         = -nr*sc2l + sum_rv_c2_nl_lu + sum_ru_c2_lu
      let valid_b = (md + md - nr % md * sc2l % md % md + sum_rv_c2_nl_lu + sum_ru_c2_lu) % md;
      let ways_v1_b = rv % md * valid_b % md;

      let _ = (c_nr_2, c_nl_2); // silence unused warnings

      ans = (ans + ways_ge2 + ways_v1_a + ways_v1_b) % md;

      *left_cnt.entry(v).or_insert(0) += 1;
    }

    ans as i32
  }
}