```rust
impl Solution {
    const MOD: i64 = 1_000_000_007;

    pub fn zig_zag_arrays(n: i32, l: i32, r: i32) -> i32 {
        let m = (r - l + 1) as usize;
        let size = 2 * m;

        // 构建转移矩阵 T (size x size)
        let mut t = vec![0i64; size * size];
        for i in 0..m {
            // newUp[i] = sum(down[0..i-1])
            for j in 0..i {
                t[i * size + (m + j)] = 1;
            }
            // newDown[i] = sum(up[i+1..m-1])
            for j in (i + 1)..m {
                t[(m + i) * size + j] = 1;
            }
        }

        // 初始向量 v (长度为1时，所有位置都为1)
        let v = vec![1i64; size];

        // 计算 T^(n-1) * v
        let exp = n - 1;
        let result_vec = Self::mat_pow_vec(&t, exp as usize, &v, size);

        let ans = result_vec.iter().fold(0, |acc, &x| (acc + x) % Self::MOD);
        ans as i32
    }

    // 计算 A^exp * v
    fn mat_pow_vec(a: &[i64], exp: usize, v: &[i64], size: usize) -> Vec<i64> {
        // 单位矩阵
        let mut result = vec![0i64; size * size];
        for i in 0..size {
            result[i * size + i] = 1;
        }

        let mut base = a.to_vec();
        let mut e = exp;
        while e > 0 {
            if e & 1 == 1 {
                result = Self::mat_mul(&result, &base, size);
            }
            e >>= 1;
            if e > 0 {
                base = Self::mat_mul(&base, &base, size);
            }
        }

        // 矩阵 × 向量
        let mut res_vec = vec![0i64; size];
        for i in 0..size {
            let mut sum = 0i64;
            let row_start = i * size;
            for j in 0..size {
                sum = (sum + result[row_start + j] * v[j]) % Self::MOD;
            }
            res_vec[i] = sum;
        }
        res_vec
    }

    // 矩阵乘法 (size x size)，行优先存储
    fn mat_mul(a: &[i64], b: &[i64], size: usize) -> Vec<i64> {
        let mut c = vec![0i64; size * size];
        for i in 0..size {
            let a_row_start = i * size;
            let c_row_start = i * size;
            for k in 0..size {
                let aik = a[a_row_start + k];
                if aik == 0 {
                    continue;
                }
                let b_row_start = k * size;
                for j in 0..size {
                    c[c_row_start + j] = (c[c_row_start + j] + aik * b[b_row_start + j]) % Self::MOD;
                }
            }
        }
        c
    }
}
```

复杂度分析

· 时间复杂度：O((2m)^3 \log n)，其中 m = r-l+1 \le 75，矩阵大小 150，快速幂约 30 次乘法。
· 空间复杂度：O(m^2)。

关键说明

1. 状态向量：前 m 个为 up，后 m 个为 down。
2. 转移矩阵：
   · T[i][m+j] = 1（当 j < i）：上升状态累加下降的较小值
   · T[m+i][j] = 1（当 j > i）：下降状态累加上升的较大值
3. 初始向量：长度为 1 时，每个值都单独成数组，up 和 down 都为 1。
4. 快速幂：矩阵乘法使用 ikj 顺序，跳过零元素优化性能。
5. 取模：所有运算在 i64 范围内完成，每次乘法后取模防止溢出。

示例验证

```rust
// n=3, l=1, r=3 -> 10
// n=3, l=4, r=5 -> 2
```