[AdditionalFile5528.zip](file://AdditionalFile5528.zip?type=additional_file)

#5528. 「PA 2018 Final」System dwu-dziesiętny

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 PA 2018 Final System dwu-dziesiętny

比特西亚是一个发达国家，拥有众多数学和算法专家。然而，在当今时代，这还不够。比特西亚政府决定开始研发量子计算机，以高效解决最复杂的问题。第一步是将二进制系统和十进制系统结合起来。

十进制系统的基数为 $10$，使用的数字范围是从 $0$ 到 $9$。通常，最低有效位位于记录的末尾，例如：

$$306 = 6 \cdot 10^{0} + 0 \cdot 10^{1} + 3 \cdot 10^{2} = 6 + 0 + 300$$

二-十进制系统同样使用数字 $0$ 到 $9$，但其基数为 $2$。在二-十进制系统中记录的数字将标注为 $(2;10)$，例如：

$$306_{(2;10)} = 6 \cdot 2^{0} + 0 \cdot 2^{1} + 3 \cdot 2^{2} = 6 + 0 + 12 = 18$$

因此，二-十进制系统中的 $306_{(2;10)}$ 表示十进制系统中的 $18$。

技术进步总是伴随着后果。在这种情况下，后果是数字记录的非唯一性。

对于十进制数 $x$，令 $f(x)$ 表示在二-十进制系统中表示 $x$ 的方式数量。例如，$f(5)=4$，因为在该系统中表示 $5$ 有四种方式：

$$\begin{gathered} 5_{(2;10)} \\ 13_{(2;10)} \\ 21_{(2;10)} \\ 101_{(2;10)} \end{gathered}$$

对于给定的数字 $L$ 和 $R$，你的任务是计算 $f(L) + f(L+1) + \ldots + f(R)$ 的总和，并输出其对 $10^{9}+7$ 取模的结果。

输入格式

输入的唯一一行包含两个整数 $L$ 和 $R$ $(1 \leq L \leq R \leq 10^{18})$。

输出格式

输出应为一个数字，表示 $(f(L) + f(L+1) + \ldots + f(R)) \bmod (10^{9}+7)$ 的值。

样例

输入

5 12

输出

80

• $f(5)=4$
• $f(6)=6$
• $f(7)=6$
• $f(8)=10$
• $f(9)=10$
• $f(10)=13$
• $f(11)=13$
• $f(12)=18$

总和为 $4 + 6 + 6 + 10 + 10 + 13 + 13 + 18 = 80$。