烦人的数学作业(Annoying Math Homework)

题目描述

NOIP2018 初赛结束了，但 H 还是要上学的啊啊。。上学肯定要完成老师布置的作业，H 十分头疼。在如山的作业中，Mr.G 布置的数学作业最烦人，H 总是完不成~~

Mr.G 最近在看一些关于数字题的书，他每天愁同学们太聪明了，所有的作业同学们都能做到全对（拿到答案）。Mr.G 蒙在鼓里（心知肚明）。为了使同学们进步，Mr.G 总是创造一些简单（毒瘤）题来作为作业。以下是数学作业的最后一题题干——

给出一个区间 $[L, R] (1 \leq L \leq R \leq 10^2)$，求区间内每个数的数字和，如 $123$ 这个数的数字和为 $1+2+3=6$。

同学们纷纷做出来了，Mr.G 一看这最后一题跟摆设没区别了呀，于是他迅速修改了题目，把范围定得非常非常大 $( 1 \leq L \leq R \leq 10^{18} )$，且有 $T(1 \leq T \leq 20)$ 组数据，将最终的答案 ${} \bmod 10^9+7$。

同学们纷纷被难住了。但 H 为了备战 NOIP2018，没有时间完成 Mr.G 的数学作业 （其实是不想做 QwQ），所以 Ta 找到了你，希望你帮助 Ta 和同学完成这烦人的数学作业！

输入格式

输入共 $T+1$ 行；

第 $1$ 行读入 $T$。代表有 $T$ 组数据；

第 $2 \sim T+1$ 行。读入 $L_i$ 和 $R_i$。

输出格式

输出共 $T$ 行，

每行输出 $L_i$ 和 $R_i$ 的区间数字和 ${} \bmod 10^9+7$。

样例输入 #1

2
24 69
70 120

样例输出 #1

411
498

数据范围

对于 $50\%$ 的数据，$1 \leq L \leq R \leq 10^8$；

对于 $100\%$ 的数据，$1 \leq L \leq R \leq 10^{18}$，$1 \leq T \leq 20$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1700。

测试点分布

出处：原题链接