Number of ways to build sturdy brick wall

impl Solution {
  pub fn build_wall(height: i32, width: i32, bricks: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let width = width as usize;
    
    // Step 1: Generate all valid row configurations (as sets of join positions)
    let mut rows: Vec<u32> = Vec::new();
    Self::gen_rows(0, width, 0, &bricks, &mut rows);
    
    if rows.is_empty() {
      return 0;
    }
    
    let k = rows.len();
    
    // Step 2: Build compatibility matrix (two rows are compatible if they don't share join positions)
    let mut compat: Vec<Vec<usize>> = vec![vec![]; k];
    for i in 0..k {
      for j in 0..k {
        if rows[i] & rows[j] == 0 {
          compat[i].push(j);
        }
      }
    }
    
    // Step 3: DP over height
    let mut dp = vec![1i64; k];
    
    for _ in 1..height {
      let mut ndp = vec![0i64; k];
      for i in 0..k {
        for &j in &compat[i] {
          ndp[i] = (ndp[i] + dp[j]) % MOD;
        }
      }
      dp = ndp;
    }
    
    let ans: i64 = dp.iter().sum::<i64>() % MOD;
    ans as i32
  }
  
  fn gen_rows(pos: usize, width: usize, joins: u32, bricks: &[i32], rows: &mut Vec<u32>) {
    if pos == width {
      rows.push(joins);
      return;
    }
    for &b in bricks {
      let new_pos = pos + b as usize;
      if new_pos > width {
        continue;
      }
      if new_pos == width {
        Self::gen_rows(new_pos, width, joins, bricks, rows);
      } else {
        Self::gen_rows(new_pos, width, joins | (1 << new_pos), bricks, rows);
      }
    }
  }
}