Untitled

class Solution {
public:
  const int mod = 1e9 + 7;
  int countArrays(vector<int>& digitSum) {
    int n = digitSum.size();
    auto digsum = [&] (int x){
      int s = 0;
      while (x){s += x % 10; x /= 10;}
      return s;
    };
    vector<vector<int>> v(51);
    for (int i = 0; i < 5001; i++){
      v[digsum(i)].push_back(i);
    }
    vector<vector<int>> dp(n);
    for (int i = 0; i < n; i++){
      if (i != 0) {
        dp[i].assign(v[digitSum[i]].size(), 0);
      } else {
        dp[i].assign(v[digitSum[i]].size(), 1);
      }
    }
    for (int i = 0; i < n - 1; i++){
      for (int j = 0; j < dp[i].size(); j++){
        auto it = lower_bound(v[digitSum[i + 1]].begin(), v[digitSum[i + 1]].end(), v[digitSum[i]][j]);
        if (it == v[digitSum[i + 1]].end()) continue;
        int idx = it - v[digitSum[i + 1]].begin();
        dp[i + 1][idx] = (dp[i + 1][idx] + dp[i][j]) % mod;
      }
      for (int j = 1; j < dp[i + 1].size(); j++){
        dp[i + 1][j] = (dp[i + 1][j] + dp[i + 1][j - 1]) % mod;
      }
    }
    long long ans = 0;
    for (int i = 0; i < dp[n - 1].size(); i++){
      ans += dp[n - 1][i];
      ans %= mod;
    }
    return ans;
  }
};