H. Cipher
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

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 li ≤ x ≤ ri and lj ≤ y ≤ rj 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.

Input

The first line contains number n. Following that are n lines, where the ith line contains pair of numbers li ri.

1 ≤ n ≤ 105
1 ≤ li ≤ ri ≤ 1018
Output

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

Example
Input
4
1 4
7 9
6 7
2 8
Output
42