0

Optimize The Code

Difficulty: MEDIUM
Contributed By
Avg. time to solve
30 min
Success Rate
60%

Problem Statement

While practicing questions on data structures, Ninja faced a problem and was not able to pass all the test cases of a question as the time complexity of the code Ninja made was very large. Ninja asked you for help. You are given a snippet of code and you have to optimize the code.

Pseudocode:

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

You are given the integers ‘A’, ‘B’, ‘C’, and ‘D’, and ‘^’ represents the bitwise XOR operator. As the result can be large print the result modulo 1000000007.

Input Format :
The first line of the input contains a single integer 'T', representing the number of test cases.

The first line of each test case contains 4 space-separated integers, representing the integers ‘A’, ‘B’, ‘C’, and ‘D’.
Output Format :
For each test case, print the result of the code modulo 1000000007.

Print the output of each test case in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= A <= B <= 5*10^3
1 <= C <= D <= 5*10^3

Time Limit : 1 sec
Sample Input 1 :
2
2 3 7 8
1 1 1 1
Sample Output 1 :
30
0
Explanation For Sample Input 1 :
For the first test case :

The operations performed will be : 2^7 + 2^8 + 3^7 + 3^8 = 5 + 10 + 4 + 11 = 30

For the second test :

The operations performed will be : 1^1 + 1^1 = 0 + 0 = 0
Sample Input 2 :
2
3 5 4 5
1 2 3 4
Sample Output 2 :
15
14
Reset Code
Full screen
copy-code
Console