题目描述

对于一个 $n$ 位的十进制数 $x (A_n,A_{n-1},\cdots,A_1)$，我们定义它的权重为：$F(x)=A_n\times 2n-1+A_{n-1}\times 2n-2+\cdots+A_1\times 20$。

现在，给你两个十进制数 $a$ 和 $b$，请计算出在闭区间 $[0, b]$ 之中，有多少个数 $x$ 的权重不大于 $a$ 的权重，即 $F(x)\le F(a)$。由于答案可能很大，你只需要输出答案对 $10^9+7$ 取模的结果即可。

输入格式

第一行一个正整数 $T$，表示测例的个数。
随后 $T$ 行，每行描述一个测例，包含两个非负整数 $a$、$b$ ，之间用空格隔开。含义见问题描述。

输出格式

对于每个测例，单独输出一行 Case #t: ans，其中 $t$ 表示测例编号，从 $1$ 开始递增，$ans$ 表示该组测例的答案（对 $10^9+7$ 取模后的结果）。

3
0 100
1 10
5 100

Case #1: 1
Case #2: 2
Case #3: 13

数据规模与约定

对于 $20\%$ 的数据，$a,b\le 10^9$；
对于 $30\%$ 的数据，$a,b\le 10^{18}$；

对于 $100\%$ 的数据，$a,b\le 10^{200}$，$T\le 5$。

样例说明

对于 Case #3，符合条件的数有 $0, 1, 2, 3, 4, 5, 10, 11, 12, 13, 20, 21, 100$，共 $13$ 个。

题目来源

By 佚名提供