Bitocja 是一个发达国家，这里不乏数学和算法专家。然而，在当今时代，这还远远不够。Bitocja 政府决定开始研发量子计算机，以有效解决最困难的问题。迈向这一目标的第一步是结合二进制和十进制系统。

十进制系统的基数是 10，数字范围从 0 到 9。通常，最低有效位位于书写顺序的末尾，例如： $$306 = 6 \cdot 10^0 + 0 \cdot 10^1 + 3 \cdot 10^2 = 6 + 0 + 300$$

“二-十进制”（dwu-dziesiętny）系统同样使用 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 有四种方式： $5_{(2;10)}$ $13_{(2;10)}$ $21_{(2;10)}$ $101_{(2;10)}$

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

输入格式

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

输出格式

输出 $(f(L) + f(L + 1) + \dots + f(R)) \pmod{10^9 + 7}$ 的值。

样例

输入 1

5 12

输出 1

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$。