// @Title: 统计整数数目 (Count of Integers)
// @Author: qisiii
// @Date: 2024-01-18 10:05:49
// @Runtime: 13 ms
// @Memory: 44.3 MB
// @comment: 
// @flag: 
class Solution {
    int min_sum, max_sum;
    int[][] dp = new int[23][401];
    int mod=1000000007;

    public int count(String num1, String num2, int min_sum, int max_sum) {
        this.min_sum = min_sum;
        this.max_sum = max_sum;
        num1 = handleDown(num1);
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], -1);
        }
        return (dfs(num2.length(), 0, true, num2) - dfs(num1.length(), 0, true, num1)+mod) % mod;
    }

    // 处理下届
    String handleDown(String num1) {
        StringBuilder r = new StringBuilder(num1);
        int jian = 1;
        for (int i = num1.length() - 1; i >= 0; i--) {
            if (jian == 1) {
                if (num1.charAt(i) > '0') {
                    r.setCharAt(i, (char) (num1.charAt(i) - 1));
                    break;
                } else {
                    r.setCharAt(i, '9');
                }
            }
        }
        return r.toString();
    }

    int dfs(int pos, int qn, boolean flag, String upper) {
        if(qn>max_sum){
            return 0;
        }
        if (pos <= 0) {
            // 当累加完最后一位的时候
            if (qn >= min_sum && qn <= max_sum) {
                return 1;
            }
            return 0;
        }
        if (!flag && dp[pos][qn] != -1) {
            return dp[pos][qn];
        }
        int ret = 0;
        int max = flag ? upper.charAt(upper.length() - pos) - '0' : 9;
        for (int i = 0; i <= max; i++) {
            ret =(ret+dfs(pos - 1, qn + i, flag && i == max, upper))%mod;
        }
        if (!flag) {
            dp[pos][qn] = ret;
        }
        return ret;
    }
}

// @Title: 统计整数数目 (Count of Integers)
// @Author: qisiii
// @Date: 2024-01-17 23:23:44
// @Runtime: 13 ms
// @Memory: 44.2 MB
// @comment: 参考标准答案写的数位DP
// @flag: WHITE
class Solution {
    int min_sum, max_sum;
    int[][] dp = new int[23][401];
    int mod=1000000007;

    public int count(String num1, String num2, int min_sum, int max_sum) {
        this.min_sum = min_sum;
        this.max_sum = max_sum;
        num1 = handleDown(num1);
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], -1);
        }
        return (dfs(num2.length(), 0, true, num2) - dfs(num1.length(), 0, true, num1)+mod) % mod;
    }

    // 处理下届
    String handleDown(String num1) {
        StringBuilder r = new StringBuilder(num1);
        int jian = 1;
        for (int i = num1.length() - 1; i >= 0; i--) {
            if (jian == 1) {
                if (num1.charAt(i) > '0') {
                    r.setCharAt(i, (char) (num1.charAt(i) - 1));
                    break;
                } else {
                    r.setCharAt(i, '9');
                }
            }
        }
        return r.toString();
    }

    int dfs(int pos, int qn, boolean flag, String upper) {
        if(qn>max_sum){
            return 0;
        }
        if (pos <= 0) {
            // 当累加完最后一位的时候
            if (qn >= min_sum && qn <= max_sum) {
                return 1;
            }
            return 0;
        }
        if (!flag && dp[pos][qn] != -1) {
            return dp[pos][qn];
        }
        int ret = 0;
        int max = flag ? upper.charAt(upper.length() - pos) - '0' : 9;
        for (int i = 0; i <= max; i++) {
            ret =(ret+dfs(pos - 1, qn + i, flag && i == max, upper))%mod;
        }
        if (!flag) {
            dp[pos][qn] = ret;
        }
        return ret;
    }
}