P3413 SAC#1 - Cute Numbers

This problem is provided by SOL, the world's most "juruo" (noob). The Jiyue City website is the official site of the Perfect Information Classroom. Address: .

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$).

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

Output a single line containing one integer, the answer.

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