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 <= 3。 对于30%的数据,n <= 6。 对于60%的数据,n <= 9。 对于全部的数据,n <= 1000,l < r。