Problem Description

Define the distance between two integers $A, B$ as the sum of the absolute differences of the digits in each corresponding position, denoted by $\operatorname{dist}(A,B)$. In particular, if $A$ and $B$ have different numbers of digits, pad the shorter one with leading zeros. 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$.

Now, given two integers $L, R$, compute the sum of distances over all ordered pairs of integers within the interval $[L, R]$. Since the answer may be very large, take it modulo $\bf 10^9+7$.

Input Format

The input consists of one line containing two integers $L, R$.

Output Format

Output one integer per line: the sum of distances over all ordered pairs of integers in $[L, R]$, modulo $\bf 10^9+7$.

1 5

40

288 291

76

1000000 10000000

581093400

Hint

[Sample 2 Explanation]

All distances between integer pairs in $[288,291]$ are:

• $\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$.

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

[Constraints and Limits]

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

[Source]

This problem comes from COCI 2013-2014 CONTEST 3 T5 PAROVI, and follows the original testdata settings, with a full score of $140$ points.

Translated and整理 provided by Eason_AC.

Translated by ChatGPT 5