Count numbers with non decreasing digits

impl Solution {
  pub fn count_numbers(l: String, r: String, b: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let b = b as u32;

    // f(n) = count of integers in [0, n] with non-decreasing base-b digits
    let r_base_b = to_base_b(&r, b);
    let fr = count_nondecreasing(&r_base_b, b);

    let fl = if let Some(l1) = decimal_subtract_one(&l) {
      let l1_base_b = to_base_b(&l1, b);
      count_nondecreasing(&l1_base_b, b)
    } else {
      0 // l = "0" => l-1 is negative, so f(l-1) = 0
    };

    ((fr - fl + MOD) % MOD) as i32
  }
}

/// Convert decimal string to base-b digits (most significant first).
fn to_base_b(decimal_str: &str, b: u32) -> Vec<u32> {
  let mut num: Vec<u32> = decimal_str.bytes().map(|c| (c - b'0') as u32).collect();
  let mut result = Vec::new();

  loop {
    // Check if num == 0
    if num.iter().all(|&d| d == 0) { break; }

    // Long division: num / b, get remainder
    let mut rem = 0u32;
    let mut new_num = Vec::new();
    for &d in &num {
      let cur = rem * 10 + d;
      let q = cur / b;
      rem = cur % b;
      if !new_num.is_empty() || q > 0 {
        new_num.push(q);
      }
    }
    result.push(rem);
    num = if new_num.is_empty() { vec![0] } else { new_num };
  }

  if result.is_empty() { result.push(0); }
  result.reverse();
  result
}

/// f(n): count integers in [0, n] with non-decreasing base-b digits.
/// n is given as base-b digits (most significant first).
fn count_nondecreasing(digits: &[u32], b: u32) -> i64 {
  const MOD: i64 = 1_000_000_007;
  let d = digits.len();
  let b = b as usize;

  // dp[last][tight]: dp[last][tight] = count of valid partial sequences
  // Initial: "haven't started", last=0 (so any d[0]>=0 valid), tight=1
  let mut dp = vec![[0i64; 2]; b];
  dp[0][1] = 1;

  for pos in 0..d {
    let mut new_dp = vec![[0i64; 2]; b];
    let lim = digits[pos] as usize;
    for last in 0..b {
      for tight in 0..2usize {
        let cnt = dp[last][tight];
        if cnt == 0 { continue; }
        let max_d = if tight == 1 { lim } else { b - 1 };
        let start = last; // next digit >= last (non-decreasing)
        for nd in start..=max_d {
          let nt = if tight == 1 && nd == lim { 1 } else { 0 };
          new_dp[nd][nt] = (new_dp[nd][nt] + cnt) % MOD;
        }
      }
    }
    dp = new_dp;
  }

  dp.iter().flat_map(|row| row.iter()).sum::<i64>() % MOD
}

/// Subtract 1 from a decimal string. Returns None if input is "0".
fn decimal_subtract_one(s: &str) -> Option<String> {
  if s == "0" { return None; }
  let mut digits: Vec<u8> = s.bytes().map(|c| c - b'0').collect();
  let n = digits.len();
  let mut i = n - 1;
  loop {
    if digits[i] > 0 {
      digits[i] -= 1;
      break;
    } else {
      digits[i] = 9;
      if i == 0 { break; }
      i -= 1;
    }
  }
  // Remove leading zeros
  let start = digits.iter().position(|&d| d != 0).unwrap_or(n - 1);
  Some(digits[start..].iter().map(|&d| (b'0' + d) as char).collect())
}