统计整数数目

题目描述

给你两个数字字符串 $num1$ 和 $num2$ ，以及两个整数 $max_{sum}$ 和 $min_{sum}$ 。如果一个整数 $x$ 满足以下条件，我们称它是一个好整数：

• $num1 <= x <= num2$
• $min_sum <= digit_sum(x) <= max_sum$.

请你返回好整数的数目。答案可能很大，请返回答案对 $109 + 7$ 取余后的结果。

注意，$digit_sum(x)$ 表示 $x$ 各位数字之和。

输入格式

第一行两个空格分隔的数字字符串分别为 $num1$ 和 $num2$；

第二行两个空格分开的整数分别表示 $min_{sum}$ 和 $max_{sum}$。

输出格式

一行一个整数表示答案。

示例 1：

1 12
1 8

11

解释: 总共有 11 个整数的数位和在 1 到 8 之间，分别是 1,2,3,4,5,6,7,8,10,11 和 12 。所以我们返回 11 。

示例 2：

1 5
1 5

5

解释: 数位和在 1 到 5 之间的 5 个整数分别为 1,2,3,4 和 5 。所以我们返回 5 。

提示：

• $1 <= num1 <= num2 <= 10^22$
• $1 <= min_sum <= max_sum <= 400$

SOURCE

统计整数数目