题目内容

定义$f(d)$为$d$的最大数位的值 例如:

$f(1012)=max(1,0,1,2)=2$

$f(988)= max(9,8,8)=9$

由于答案可能很大，请求出$\sum_{i=x}^{y}f(i)$ 在模$10^9+7$ 意义下的取值。

输入描述

输入两个整数$x,y$。

$1 \leq x \leq y \leq 10^{18}$

输出描述

输出一个非负整数，表示答案

样例

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

7 8

输出

15

说明

$\sum_{i=7}^{8}f(i)=f(7)+f(8)=15$

样例2

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

2 202

输出

1236

思路:数位dp模板题

先跟着灵神学一下 数位dp

然后你就会了...

因为其实就是一个非常裸的数位dp。刷过哪怕一道数位dp的题，你就能够立马反应过来。

在模板的基础上做一个更改:dfs的过程中转移当前数位的最大值$mx$。递归出口返回$mx$即可。