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