Description

给定两个非负整数 $X$ 和 $Y$，计算以下值：

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

对 $10^9+7$ 取模，其中

• $\&$ 表示按位与运算；
• $[A]$ 的值为 1 如果 $A$ 为真，否则为 0；
• $\lfloor x\rfloor$ 表示不大于 $x$ 的最大整数。

Input Format

第一行包含一个整数 $T\,(1\le T \le 10^5)$，表示测试用例的数量。

接下来的 $T$ 行中，每行包含两个整数 $X, Y\,(0\le X,Y \le 10^9)$，表示一个测试用例。

Output Format

对于每个测试用例，输出一行一个整数，表示该测试用例的答案。

3
3 3
19 26
8 17

14
814
278

Hint

对于第一个测试用例：

• 两个 $(i,j)$ 对使得和增加 1：$(0, 1), (1, 0)$
• 六个 $(i,j)$ 对使得和增加 2：$(0, 2), (0, 3), (1, 2), (2, 0), (2, 1), (3, 0)$

所以答案是 $1\times 2 + 2\times 6 = 14$。

题面翻译由 ChatGPT-4o 提供。