Counting Problem

Points: 17

Time limit: 1.0s

Memory limit: 256M

Author:

Problem type

Given two integers $N$ ~N~ and $M$ ~M~, count the number of ordered pairs of integers $(x, y)$ ~(x, y)~ in the range $[1, N)$ ~[1, N)~ such that $x + y \geq N$ ~x + y \geq N~ and $x \oplus y \leq M$ ~x \oplus y \leq M~. Since the answer may be very large, output it modulo $10^9 + 7$ ~10^9 + 7~.

There will be $T$ ~T~ such test cases.

Constraints

$1 \leq T \leq 10^4$ ~1 \leq T \leq 10^4~

$2 \leq N \leq 10^{18}$ ~2 \leq N \leq 10^{18}~

$0 \leq M \leq 10^{18}$ ~0 \leq M \leq 10^{18}~

Input Specification

The first line contains an integer $T$ ~T~.

The new $T$ ~T~ line contains two integers, $N$ ~N~ and $M$ ~M~.

Output Specification

Output a single integer, the number of pairs modulo $10^9 + 7$ ~10^9 + 7~.

Sample Input

1
5 6

Sample Output

Explanation for Sample

The pairs are $(1, 4)$ ~(1, 4)~, $(2, 3)$ ~(2, 3)~, $(2, 4)$ ~(2, 4)~, $(3, 2)$ ~(3, 2)~, $(3, 3)$ ~(3, 3)~, $(4, 1)$ ~(4, 1)~, $(4, 2)$ ~(4, 2)~, $(4, 4)$ ~(4, 4)~.

Comments

There are no comments at the moment.