eolymp
bolt
Try our new interface for solving problems
Problems

U-turn bits 2

U-turn bits 2

Time limit 2 seconds
Memory limit 256 MiB

Пусть n = 2^s, где s0 — целое число. Для каждого целого 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.

Input data

The first line of the input file contains an integer s (0s25). The second line contains an integer k — the number of queries (1k5·10^5). The next k lines contains the query itself - a pair of integers l, r (0lr < 2^s).

Output data

The output file output k numbers - the answers to these requests.

Examples

Input example #1
3
1
3 3
Output example #1
6
Author Dmitriy Zhukov
Source Winter School, Kharkov, 2011, Day 2