P3413 SAC#1 - 萌数

题目背景

本题由世界上最蒟蒻的 SOL 提供。

寂月城网站是完美信息教室的官网。地址：http://191.101.11.174/mgzd。

题目描述

蒟蒻 SOL 居然觉得数很萌！

好在在他眼里，并不是所有数都是萌的。只有满足“存在长度至少为 22 的回文子串”的数是萌的——也就是说，101 是萌的，因为 101 本身就是一个回文数；110 是萌的，因为包含回文子串 11；但是 102 不是萌的，1201 也不是萌的。

现在 SOL 想知道从l  到 r 的所有整数中有多少个萌数。

由于答案可能很大，所以只需要输出答案对 1000000007（10^9+7）的余数。

输入格式

输入包含仅 1 行，包含两个整数：l，r。

输出格式

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

题解

因为所要求的区间相当的大，因此我们不妨从它的数位入手进行dpdp。

根据萌数的性质，倘若要满足一个长度为lenlen的字符串是萌数，那么这个串只需至少包含一个长度为22（对应偶回