Пусть \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{25}). Во второй строке записано целое число \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} чисел --- ответы на соответствующие запросы.