题目描述

定义两个整数 $A,B$ 之间的距离为这两个整数所有对应位上的数的差的绝对值之和，记为 $\operatorname{dist}(A,B)$。特别地，如果 $A,B$ 两数的位数不相同，则在位数较小的数前补足前导 $0$。例如：

• $\operatorname{dist}(4561,3278)=\left|4-3\right|+\left|5-2\right|+\left|6-7\right|+\left|1-8\right|=12$。
• $\operatorname{dist}(32,5678)=\left|0-5\right|+\left|0-6\right|+\left|3-7\right|+\left|2-8\right|=21$。

现在，给定两个整数 $L,R$，请你求出所有在区间 $[L,R]$ 内的整数对的距离和。由于答案可能很大，因此请对 $\bf 10^9+7$ 取模。

输入格式

输入仅一行，包含两个整数 $L,R$。

输出格式

输出一行一个整数，表示所有在区间 $[L,R]$ 内的整数对的距离和对 $\bf 10^9+7$ 取模之后的值。

1 5

40

288 291

76

1000000 10000000

581093400

提示

【样例 2 解释】

所有在区间 $[288,291]$ 内的整数对的距离如下：

• $\operatorname{dist}(288,289)=\operatorname{dist}(289,288)=1$。
• $\operatorname{dist}(288,290)=\operatorname{dist}(290,288)=9$。
• $\operatorname{dist}(288,291)=\operatorname{dist}(291,288)=8$。
• $\operatorname{dist}(289,290)=\operatorname{dist}(290,289)=10$。
• $\operatorname{dist}(289,291)=\operatorname{dist}(291,289)=9$。
• $\operatorname{dist}(290,291)=\operatorname{dist}(291,290)=1$。

因此距离和为 $2\times (1+9+8+10+9+1)=76$。

【数据范围与限制】

对于 $20\%$ 的数据，满足 $A,B\leqslant 10^4$。
对于 $40\%$ 的数据，满足 $A,B\leqslant 10^{100}$。
对于所有数据，$1\leqslant A\leqslant B\leqslant 10^{50000}$。

【题目来源】

本题来源自 COCI 2013-2014 CONTEST 3 T5 PAROVI，按照原题数据配置，满分 $140$ 分。

由 Eason_AC 翻译整理提供。