该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小明有一个盒子，一开始盒子里面没有球。

球一共有 $2^{31}$ 种类型，分别是编号为 $[0,2^{30}-1]$ 的白色球，以及编号为 $[0,2^{30}-1]$ 的黑色球。

假设现在小明的盒子里一共有 $k$ 个球，第 $i(1\leq i\leq k)$ 个球的编号是 $a_i$，颜色是 $b_i$（$b_i=1$ 代表白色球，$b_i=-1$ 代表黑色球）。

那么，定义小明盒子现在的价值 $F$ 是：

$F=\sum_{i=1}^{k}\sum_{j=1}^k b_i\times b_j\times \text{lcp}(a_i,a_j)$。

其中，$\text{lcp}(x,y)$ 表示的是，把数字 $x,y$ 分别转换成长度为 $30$ 的二进制数字串（可能含前导 $0$）后，这两个二进数字串的最长公共前缀长度。

例如 $\text{lcp}(3,5)=27$，因为 $(3)_2=000000000000000000000000000011,(5)_2=000000000000000000000000000101$，它俩的最长公共前缀长度是 $27$。

现在，小明会执行 $Q$ 轮操作，每轮操作形如 l,r,k。

如果 $k>0$，则小明会对于每一个 $i∈[l,r]$，执行下述操作 $k$ 次：如果盒子里有编号为 $i$ 的黑色球，则从盒子中拿出一个，如果盒子里没有编号为 $i$ 的黑色球，则往盒子中加入一个编号为 $i$ 的白色球。

如果 $k<0$，则小明会对于每一个 $i∈[l,r]$，执行下述操作 $k$ 次：如果盒子里有编号为 $i$ 的白色球，则从盒子中拿出一个，如果盒子里没有编号为 $i$ 的白色球，则往盒子中加入一个编号为 $i$ 的黑色球。

请帮助小明，在每一轮操作结束后，输出当前盒子的价值 $\mod 10^9+7$。

输入格式

第一行输入 $Q$。

接下来 $Q$ 行，每一行输入 $l,r,k$。

输出格式

输出 $Q$ 行，每行一个数字表示答案 $\mod 10^9+7$。

样例输入 #1

4
0 3 1
0 3 1
0 2 -1
0 3 -1

样例输出 #1

460
1840
720
30

下发文件

数据范围

本题共 20 个测试点。

对于全部测试数据：$1\leq Q\leq 2\times 10^5,0\leq l\leq r<2^{30}，1\leq |k|<2^{30}$。