Distance Between Two Integers

Time limit3sMemory limit128 MB

Summary

Sum the digitwise absolute differences over every ordered pair of integers from A to B, modulo 1,000,000,007.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

The distance between two integers is the sum of the absolute differences of their digits, compared position by position. For example, the distance between 4561 and 3278 is $|4 - 3| + |5 - 2| + |6 - 7| + |1 - 8| = 12$ . When the two numbers have different lengths, the shorter one is padded with leading zeros so that the positions line up. The distance between 32 and 5678 is therefore $|0 - 5| + |0 - 6| + |3 - 7| + |2 - 8| = 21$ .

Given two integers $A$ and $B$ , write a program that adds up the distance of every ordered pair $(x, y)$ in the interval $[A, B]$ . The reversed pair $(y, x)$ is counted separately, and $x = y$ is included as well, with distance 0.

Input

The first line contains two integers $A$ and $B$ separated by a space. ( $1 \le A \le B \le 10^{50000}$ )

Output

Print the sum of the distances of all ordered pairs in the interval $[A, B]$ on the first line. The answer can grow very large, so print it modulo 1,000,000,007.

Examples3

Example 1
Input
```
1 5
```
Expected output
```
40
```
Example 2
Input
```
288 291
```
Expected output
```
76
```
Example 3
Input
```
1000000 10000000
```
Expected output
```
581093400
```