H. Шифр
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Устав изобретать велосипед, Леша решил изобрести абсолютно стойкий шифр. Матёрый криптоаналитик Вася прознал, что Лёша использует в своем алгоритме только такие x и y, что li ≤ x ≤ ri и lj ≤ y ≤ rj для 1 ≤ i < j ≤ n. Помогите Васе взломать тайное послание Лёши. Для этого найдите количество четвёрок чисел x y i j таких, что количество единиц в двоичном представлении значения нечетно.

 — сложение по модулю 2, исключающее ИЛИ, строгая дизъюнкция, xor, поразрядное дополнение, побитовый комплемент.

Входные данные

В первой строке задается число n. В следующих n строках задаются пары чисел li ri.

1 ≤ n ≤ 105
1 ≤ li ≤ ri ≤ 1018
Выходные данные

В единственной строке выведите количество искомых четверок по модулю 109 + 7.

Пример
Входные данные
4
1 4
7 9
6 7
2 8
Выходные данные
42