SAC#1 - 萌数

题目背景

本题由世界上最蒟蒻的 SOL 提供。 寂月城网站是完美信息教室的官网。地址:<http://191.101.11.174/mgzd>。

题目描述

蒟蒻 SOL 居然觉得数很萌! 好在在他眼里,并不是所有数都是萌的。只有满足“存在长度至少为 $2$ 的回文子串”的数是萌的——也就是说,$101$ 是萌的,因为 $101$ 本身就是一个回文数;$110$ 是萌的,因为包含回文子串 $11$;但是 $102$ 不是萌的,$1201$ 也不是萌的。 现在 SOL 想知道从 $l$ 到 $r$ 的所有整数中有多少个萌数。 由于答案可能很大,所以只需要输出答案对 $1000000007$($10^9+7$)的余数。

输入输出格式

输入格式


输入包含仅 $1$ 行,包含两个整数:$l$,$r$。

输出格式


输出仅 $1$ 行,包含一个整数,即为答案。

输入输出样例

输入样例 #1

1 100

输出样例 #1

10

输入样例 #2

100 1000

输出样例 #2

253

说明

记 $n$ 为 $r$ 在 $10$ 进制下的位数。 对于 $10\%$ 的数据,$n \le 3$。 对于 $30\%$ 的数据,$n \le 6$。 对于 $60\%$ 的数据,$n \le 9$。 对于全部的数据,$n \le 1000$,$l < r$。 ------------ 2024/2/4 添加一组 hack 数据。