A quick question is a good question. Calculate the following sum:
~\sum_{x=l}^{r} \text{XOR}(1, 2, ..., x)~
Input
The first line consists of two integers 
~l \; r~, representing the parameters for the sum. The following conditions hold:
~1 \leq l, r \leq 10^{15}~
~1 \leq r - l \leq 10^{6}~
Output
Output the value of the sum.
Note: Since the answer may be very large, return it modulus 
~10^9 + 7~.
Example
Input
4 6
Output
12
~\text{XOR}(1, 2, ..., 4) = 4~
~\text{XOR}(1, 2, ..., 5) = 1~
~\text{XOR}(1, 2, ..., 6) = 7~
The sum of these XORs is 
~12~, so 
~\sum_{x=5}^{7} \text{XOR}(1, 2, ..., x) = 12~.
Comments
I think the l, r range is a bit too large LMAO! 10^15 is insane. I'm assuming it's supposed to be 10^5? Edit: nvm it's hard for a reason.