Поворот бітів
Нехай n = 2^s, де s ≥ 0 — ціле число. Для кожного цілого i від 0 до n-1 визначимо значення a_i наступним чином. Нехай b_{s-1}...b_1b_0 — запис числа i у двійковій системі числення (при необхідності доповнена ліворуч нулями до довжини s). Переставимо ці біти у зворотному порядку (b_0b_1...b_{s-1}). Тоді значенням a_i буде число, двійковим записом якого є b_0b_1...b_{s-1}.
Наприклад, s = 3, i = 3, тоді двійковий запис буде виглядати, як 011_2, а запис у зворотному порядку — 110_2, відповідно, якщо s = 3, то a_3 = 6.
Потрібно для заданого числа s швидко відповідати на запити про підрахунок суми a_l+a_{l+1}+...+a_r по модулю 1000000007.
Вхідні дані
У першому рядку вхідного файлу записано ціле число s (0 ≤ s ≤ 31). У другому рядку записано ціле число k — кількість запитів (1 ≤ k ≤ 5·10^5). У наступних k рядках містяться самі запити — пари цілих чисел l, r (0 ≤ l ≤ r < 2^s).
Вихідні дані
У вихідний файл виведіть k чисел — відповіді на відповідні запити.