题目描述

Given two non-negative integers $X$ and $Y$, determine the value of

$$\sum_{i=0}^{X}\sum_{j=[i=0]}^{Y}[i\&j=0]\lfloor\log_2(i+j)+1\rfloor $$

modulo $10^9+7$ where

• $\&$ denotes bitwise AND;
• $[A]$ equals 1 if $A$ is true, otherwise $0$;
• $\lfloor x\rfloor$ equals the maximum integer whose value is no more than $x$.

输入格式

The first line contains one integer $T\,(1\le T \le 10^5)$ denoting the number of test cases.

Each of the following $T$ lines contains two integers $X, Y\,(0\le X,Y \le 10^9)$ indicating a test case.

输出格式

For each test case, print one line containing one integer, the answer to the test case.

题目大意

给定两个非负整数 $X,Y$，计算下列式子对 $10^9+7$ 取模的值：

$$\sum\limits_{i=0}^{X}{\sum\limits_{j=[i=0]}^{Y}{[i \& j=0]\lfloor \log_2(i+j)+1\rfloor}} $$

其中：

• $\&$ 表示按位与。
• $[A]$ 等于 $1$，当且仅当表达式 $A$ 为真；否则 $[A]$ 等于 $0$。
• $\lfloor x \rfloor$ 表示不大于 $x$ 的最大整数。

3
3 3
19 26
8 17

14
814
278

提示

For the first test case:

• Two $(i,j)$ pairs increase the sum by 1: $(0, 1), (1, 0)$
• Six $(i,j)$ pairs increase the sum by 2: $(0, 2), (0, 3), (1, 2), (2, 0), (2, 1), (3, 0)$

So the answer is $1\times 2 + 2\times 6 = 14$.