Description

The newbie SOL thinks numbers are cute!

Fortunately, not all numbers are cute in his eyes. A number is cute if and only if there exists a palindromic substring of length at least $2$—that is, 101 is cute because 101 itself is a palindrome; 110 is cute because it contains the palindromic substring 11; but 102 is not cute, and 1201 is not cute.

Now SOL wants to know how many cute numbers there are among all integers from $l$ to $r$.

Since the answer may be large, output the answer modulo $1000000007$ ($10^9+7$).

Input Format

The input contains a single line with two integers: $l$ and $r$.

Output Format

Output a single line containing one integer, the answer.

1 100

10

100 1000

253

Hint

Let $n$ be the number of digits of $r$ in base $10$.

For $10\%$ of the testdata, $n \le 3$. For $30\%$ of the testdata, $n \le 6$. For $60\%$ of the testdata, $n \le 9$. For all the testdata, $n \le 1000$, $l < r$.

2024/2/4: One set of hack testdata was added.

Translated by ChatGPT 5