Разворот битов 2
Пусть 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 ≤ 25). Во второй строке записано целое число k — количество запросов (1 ≤ k ≤ 5·10^5). В следующих k строках содержатся сами запросы — пары целых чисел l, r (0 ≤ l ≤ r < 2^s).
Выходные данные
В выходной файл выведите k чисел — ответы на соответствующие запросы.