纳扎尔是克里姆兰王国科学学院的学生,以其出色的数学能力而闻名。今天数学老师给了他一个非常困难的任务。
考虑两个无限的数字集。第一组由奇数正数 ($$$1, 3, 5, 7, \ldots$$$) 组成,第二组由偶数正数 ($$$2, 4, 6, 8, \ldots$$$) 组成。第一阶段,老师在无尽的黑板上写下第一组的第一个数字,第二阶段——第二组的前两个数字,第三阶段——第一组的接下来的四个数字,第四阶段——第二组的接下来的八个数字,依此类推。换句话说,在每个阶段,从第二个开始,他写出的数字是前一个阶段的两倍,并且还将写出这些数字的集合更改为另一个集合。
前十个写的数字:$$$1, 2, 4, 3, 5, 7, 9, 6, 8, 10$$$。让我们对写下的数字进行编号,从 1 开始。
任务是对于给定的整数 $$$l$$$ 和 $$$r$$$ 找到从 $$$l$$$ 到 $$$r$$$ 的数字之和。答案可能很大,因此您需要找到除以 $$$1000000007$$$ ($$$10^9+7$$$) 的余数。
娜扎想了很久这个问题,但没有想出解决办法。帮他解决这个问题。
输入
第一行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq 10^{18}$$$) - 您需要求总和的范围。
输出
打印一个整数——答案以 $$$1000000007$$$ ($$$10^9+7$$$) 为模。
示例
输入 #1
1 3
输出 #1
7
输入 #2
5 14
输出 #2
105
输入 #3
88005553535 99999999999
输出 #3
761141116
注意
在第一个示例中,答案是写出的前三个数字的总和 ($$$1 + 2 + 4 = 7$$$)。
在第二个示例中,数字从 $$$5$$$ 到 $$$14$$$ 的数字:$$$5, 7, 9, 6, 8, 10, 12, 14, 16, 18$$$。他们的总和是$$$105$$$。