It's again the hiring season! Our friends at Take Off Labs wanted to go off the beaten track and challenge the aspiring engineers with some more difficult problems. Since nobody managed to solve this one during the interviews, we're giving it to you to solve. But beware that you don't have much time either, you must finish this problem before Mindcoding Round #3 ends! So, without further introductions, here it is:
You are given several queries, each of the form of a closed interval [x, y]. You are to find, for each such query, how many subintervals [i, j] exist (x ≤ i ≤ j ≤ y) such that (i AND (i+1) AND … AND j) > 0.
Since this number can be very large, you should print it modulo 109+7.
Input
The first line of input contains a single integer Q - the number of queries you have to answer.
Each of the following Q lines contain two space separated values, x and y.
Output
The output should contain the answers to all Q queries, each on a separate line.
Constraints
- 1 ≤ Q ≤ 10
- 1 ≤ x ≤ y ≤ 109
- AND refers to the bitwise operator.
Sample
| Input | Output | Explanation |
|---|---|---|
| 2 3 6 42 43 | 7 3 | In the first case, there are 7 valid intervals:
|
Haskell implementation:
solve [a, b] = (sum $ map subsequences deltas) `mod` (10^9+7) where deltas = zipWith (-) (tail interestPoints) interestPoints interestPoints = a : (dropWhile (<= a) $ takeWhile (<= b) powers) ++ [b+1] subsequences x = (x * succ x) `div` 2 powers = map (2^) [1..] main = do input <- getContents let queries = map ((map read) . words) $ (tail . lines) input sequence $ map (print . solve) queries
