Problem Description

Define the distance between two integers $A$ and $B$ as the sum of the absolute differences of their corresponding digits, denoted as $\operatorname{dist}(A,B)$. Specifically, if $A$ and $B$ have different number of digits, prepend leading zeros to the shorter number. For example:

• $\operatorname{dist}(4561,3278)=\left|4-3\right|+\left|5-2\right|+\left|6-7\right|+\left|1-8\right|=12$.
• $\operatorname{dist}(32,5678)=\left|0-5\right|+\left|0-6\right|+\left|3-7\right|+\left|2-8\right|=21$.

Given two integers $L$ and $R$, you are asked to find the sum of distances for all integer pairs within the interval $[L, R]$. Since the answer may be very large, output the result modulo $\bf 10^9+7$.

Input Format

The input consists of a single line containing two integers $L$ and $R$.

Output Format

Output a single integer, which is the sum of distances for all integer pairs within the interval $[L, R]$ modulo $\bf 10^9+7$.

Sample Input and Output

Sample Input #1

1 5

Sample Output #1

40

Sample Input #2

288 291

Sample Output #2

76

Sample Input #3

1000000 10000000

Sample Output #3

581093400

Notes

[Sample 2 Explanation]

The distances for all integer pairs within the interval $[288, 291]$ are as follows:

• $\operatorname{dist}(288,289)=\operatorname{dist}(289,288)=1$.
• $\operatorname{dist}(288,290)=\operatorname{dist}(290,288)=9$.
• $\operatorname{dist}(288,291)=\operatorname{dist}(291,288)=8$.
• $\operatorname{dist}(289,290)=\operatorname{dist}(290,289)=10$.
• $\operatorname{dist}(289,291)=\operatorname{dist}(291,289)=9$.
• $\operatorname{dist}(290,291)=\operatorname{dist}(291,290)=1$.

Thus, the sum of distances is $2 \times (1+9+8+10+9+1)=76$.

[Data Range and Constraints]

For $20\%$ of the data, $A, B \leq 10^4$.
For $40\%$ of the data, $A, B \leq 10^{100}$.
For all data, $1 \leq A \leq B \leq 10^{50000}$.

[Problem Source]

This problem is from COCI 2013-2014 CONTEST 3 T5 PAROVI, configured with the original data. Full score is $140$ points.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分