当前没有测试数据。

元阳梯田的灌溉节 (Sum of Josephus)

题目背景： 在云南元阳，哈尼族同胞开垦的梯田随山势叠层而上，蔚为壮观。每年春耕时节，哈尼族人会举行传统的灌溉祭祀。

题目描述： 元阳的一处山坡上有许多块梯田，每块梯田按高度从高到低编号为 $1, 2, 3, \dots$。在灌溉祭祀中，如果今年有 $n$ 块梯田参与祭祀，祭司会按照“猫捉老鼠”的规律（即：隔一个关掉一个水闸，第一个水闸保留，第二个关掉，依此类推）来决定最后一块保持灌溉的梯田，这块梯田被称为“丰收田”，其编号记为 $f(n)$。

例如：

• 当 $n=3$ 时，水闸关闭顺序为 2, 1，最后剩下 $f(3)=3$。
• 当 $n=5$ 时，水闸关闭顺序为 2, 4, 1, 5，最后剩下 $f(5)=3$。

哈尼小伙子阿强提出了一个难题：给定一个范围 $[L, R]$，他想知道如果参与祭祀的梯田总数分别取 $L, L+1, L+2, \dots, R$ 时，所有对应的“丰收田”编号之和是多少？即求：

由于结果可能非常大，请输出答案对 $10^9 + 7$ 取模后的结果。

【输入格式】 输入包含多组测试数据。第一行包含一个整数 $T$，表示测试组数。 接下来 $T$ 行，每行包含两个正整数 $L$ 和 $R$。

【输出格式】 对于每组数据，输出一个整数，表示区间内 $f(i)$ 的和对 $10^9 + 7$ 取模的结果。

【输入样例】

3
1 3
5 10
1 100

【输出样例】

5
24
2734

【样例解释】

• 对于 $L=1, R=3$：$f(1)=1, f(2)=1, f(3)=3$。和为 $1+1+3 = 5$。
• 对于 $L=5, R=10$： $f(5)=3, f(6)=5, f(7)=7, f(8)=1, f(9)=3, f(10)=5$。 和为 $3+5+7+1+3+5 = 24$。