% Origin: XXVI Национальная олимпиада Болгарии по информатике, 24.01.2010
% http://infoman.musala.com/index.html?211+2+%u0441%u044A%u0441%u0442%u0435%u0437%u0430%u043D%u0438%u044F%20%26gt%3B%20%u043D%u0430%u0446%u0438%u043E%u043D%u0430%u043B%u043D%u0438%20%26gt%3B%20%u0443%u0447%u0435%u043D%u0438%u0447%u0435%u0441%u043A%u0438%20%26gt%3B%20%u0437%u0438%u043C%u043D%u0438%20%u043C%u0430%u0442%u0435%u043C%u0430%u0442%u0438%u0447%u0435%u0441%u043A%u0438%20%u0441%u044A%u0441%u0442%u0435%u0437%u0430%u043D%u0438%u044F+http://infoman.musala.com/contests/winter/main.html
\begin{problem}{Разверни их. Полностью!}
%translation - romanandreev
{\textsl{стандартный ввод}}{\textsl{стандартный вывод}}
%{integer.in}{integer.out}
{3 секунды}{256 мебибайт}{}

Определим операцию $\mathrm{rev} (K, N)$ над числом $N$
от $0$ до $2^K - 1$, которая разворачивает биты в двоичной записи числа $N$.
Например, $\mathrm{rev} (4, 5) = 10$.
Вам необходимо отвечать на запросы
$$get(A, B) = (\sum\limits_{N = A}^{B} \mathrm{rev} (k, N))
  \bmod (1\,000\,000\,001)\text{.}$$

\InputFile

В первой строке входного файла заданы через пробел два целых числа $K$ и $T$
($1 \le K \le 31$, $1 \le T \le 500\,000$).
В следующих $T$ строках идут запросы, состоящие из двух целых
чисел $A$ и $B$, разделённых пробелом
$0 \le A \le B < 2^{K}$.

\OutputFile

Для каждого теста выведите на отдельной строчке ответ.

\Examples

\begin{example}%
\exmp{
3 1
3 3
}{
6
}%
\exmp{
25 2
1 16
17 16777000
}{
252706816
44924975
}%
\end{example}

\end{problem}
