Sum of Log

题号：NC214900
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

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  denoting the number of test cases.

Each of the following  lines contains two integers  indicating a test case.

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

示例1

复制

复制

14
814
278

For the first test case:
1. Two  pairs increase the sum by 1: 
2. Six  pairs increase the sum by 2: 

So the answer is .