Description

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

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

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

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

Input Format

第一行输入字符串num1。

第二行输入字符串num2。

第三行输入两个整数，分别是min_sum 和 max_sum。

• 1 <= num1 <= num2 <= 10²²
• 1 <= min_sum <= max_sum <= 400

Output Format

返回在区间[num1 ， num2] 内好整数的个数。

1
12
1 8

11

Hint

【样例1解释】

在区间[1 , 12]范围内，数位和在[1 , 8] 之间的整数个数有11个，分别是 1、2、3、4、5、6、7、8、10、11、12

Source

信奥星OJ http://127.0.0.1