Code Optimization Problem

Ninja encountered an issue with a practice problem where certain test cases could not be passed due to high time complexity. You are provided with a snippet of pseudocode, and your task is to optimize it.

Pseudocode:

RES = 0 FOR(i -> A to B) { FOR(j -> C to D) { ADD (i ^ j) to RES; } } PRINT(RES) 

The task is to compute the result of bitwise XOR operations in a given range and return the sum modulo 1000000007.

Input:

The first line contains an integer 'T', representing the number of test cases.
The subsequent lines of each test case contain 4 space-separated integers: 'A', 'B', 'C', and 'D'.

Output:

For each test case, output the result modulo 1000000007.
Provide the result of each test case on a new line.

Example:

Input:

2
1 2 1 2
3 4 3 4

Output:

12
76

Constraints:

• 1 <= T <= 10
• 1 <= A <= B <= 5*10^3
• 1 <= C <= D <= 5*10^3

Note:

You are not required to print anything explicitly; the solution should be implemented within a function.