Пусть 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.
The first line of the input file contains an integer s (0 ≤ s ≤ 25). The second line contains an integer k — the number of queries (1 ≤ k ≤ 5·10^5). The next k lines contains the query itself - a pair of integers l, r (0 ≤ l ≤ r < 2^s).
The output file output k numbers - the answers to these requests.