Interesting Numbers

Time limit1sMemory limit512 MB

Summary

Count positive integers between L and R whose decimal digits are nondecreasing, modulo 1e9+7, with L and R up to 10^100.

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

Problem

Sofia considers a number interesting if its digits are in nondecreasing order. For example, 123, 1111, and 888999 are interesting.

Sofia wonders how many interesting positive integers lie in the range from $L$ to $R$ inclusive. For large $L$ and $R$ this count can be quite large, so Sofia wants the remainder of this count modulo $10^9 + 7$ .

Write a program that, given $L$ and $R$ , determines the number of interesting numbers in the range from $L$ to $R$ inclusive and prints the remainder of this count modulo $10^9 + 7$ .

Input

The input file contains two lines. The first line contains the number $L$ , and the second line contains the number $R$ ( $1 \le L \le R \le 10^{100}$ ).

Output

The output file must contain a single integer: the remainder of the number of interesting numbers in the range from $L$ to $R$ inclusive modulo $10^9 + 7$ .

Examples1

Example 1
Input
```
1
100
```
Expected output
```
54
```