403546: GYM101192 H Cipher

Lyosha is tired of inventing a bicycle, so he decided to invent an unbreakable cipher. Mature cryptanalyst Vasya knows that in his algorithm Lyosha uses x and y such that l_i ≤ x ≤ r_i and l_j ≤ y ≤ r_j for 1 ≤ i < j ≤ n. Help Vasya decipher Lyosha’s private message. You need to compute number of tuples (x, y, i, j) such that number of ones in binary representation of is odd.

Here denotes addition modulo 2 aka exclusive disjunction aka exclusive OR aka xor.

The first line contains number n. Following that are n lines, where the i^th line contains pair of numbers l_i r_i.

The only output line should contain the number of tuples (x, y, i, j) modulo 10⁹ + 7.

4
1 4
7 9
6 7
2 8

42