题目描述

菜汪酱刚学了线段树这种数据结构，她写了这样一份代码：

void build(int i, int l, int r) {
L[i] = l; R[i] = r;
if (l == r) return;
int mid = (l+r)/2;
build(i*2, l, mid); build(i*2+1, mid+1, r);
}

对于一棵有 $n$ 个叶子的线段树，只需要执行 build(1,1,n) 就可以建出线段树。

对于给定的 $n,x,y$，她想知道满足 $x\le L[i]\le R[i]\le y$ 的 $i$ 的和是多少？

输入格式

第一行一个整数 $T$ 表示询问组数。

接下来 $T$ 行每行 $3$ 个整数 $n,x,y$ 表示一组询问。

输出格式

对于每组询问，输出一行一个整数表示满足条件的 $i$ 的和 $\bmod 10^9+7$。

样例

样例输入#1

5
4 1 4
7 3 6
20 4 15
100 22 78
1000000 114514 919810

样例输出#1

28
57
469
12244
659903510

样例输入/输出#2/#3

见下发文件。

数据范围

对于 $20\%$ 的数据，$n\le 300$。

对于 $40\%$ 的数据，$n\le 10^6$。

对于另外 $20\%$ 的数据，保证 $n=2^k$，$k$ 为非负整数。

对于另外 $20\%$ 的数据，$x=1$，$y=n$。

对于 $100\%$ 的数据，$1\le T\le 10^4$，$1\le x\le y\le n\le 10^{18}$。