impl Solution {
    pub fn num_ways(words: Vec<String>, target: String) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let word_length = words[0].len();
        let target_length = target.len();

        // Edge case: If the target is longer than the word length, it's impossible
        if target_length > word_length {
            return 0;
        }

        // Step 1: Build letter counters
        let letter_counters = Self::build_letter_counters(&words, word_length);

        // Step 2: Compute the number of ways using dynamic programming
        Self::compute_ways(&target, &letter_counters, word_length, target_length, MOD)
    }

    fn build_letter_counters(words: &Vec<String>, word_length: usize) -> [Vec<i32>; 26] {
        // Initialize a fixed-size array of 26 vectors using Default::default()
        let mut letter_counters: [Vec<i32>; 26] = Default::default();
        for vec in &mut letter_counters {
            *vec = vec![0; word_length];
        }

        for word in words {
            for (j, c) in word.bytes().enumerate() {
                letter_counters[(c - b'a') as usize][j] += 1;
            }
        }

        letter_counters
    }

    fn compute_ways(
        target: &String,
        letter_counters: &[Vec<i32>; 26],
        word_length: usize,
        target_length: usize,
        mod_val: i32,
    ) -> i32 {
        let target_bytes = target.as_bytes();

        // Initialize the DP array for the first target character
        let mut dp = vec![0; word_length];
        let first_char_counters = &letter_counters[(target_bytes[0] - b'a') as usize];

        dp[0] = first_char_counters[0];
        for j in 1..word_length {
            dp[j] = (first_char_counters[j] + dp[j - 1]) % mod_val;
        }

        // Process subsequent target characters
        for i in 1..target_length {
            let mut diag_val = 0;
            let current_char_counters = &letter_counters[(target_bytes[i] - b'a') as usize];

            diag_val = dp[i - 1];
            dp[i - 1] = 0;

            for j in i..word_length {
                let new_diag_val = dp[j];
                dp[j] = ((dp[j - 1] as i64 + diag_val as i64 * current_char_counters[j] as i64) % mod_val as i64) as i32;
                diag_val = new_diag_val;
            }
        }

        dp[word_length - 1]
    }
}