eolymp
bolt
Try our new interface for solving problems
Problems

U-turn bits

U-turn bits

Time limit 2 seconds
Memory limit 256 MiB

Let n = 2^s, where s0 — integer. For each integer i from 0 to n-1 define the value of ai follows. Let b_{s-1}...b_1b_0 — a record number i in binary notation (if necessary padded with zeros to length s). We rearrange these bits in reverse order (b_0b_1...b_{s-1}). Then the value of a_i will be a number, whose binary representation is b_0b_1...b_{s-1}.

For example, s = 3, i = 3, then the binary representation would look like 011_2, and the record in reverse order — 110_2, therefore, if s = 3, then a_3 = 6.

Required for a given number s of rapidly responding to the calculation of the sum a_l+a_{l+1}+...+a_r modulo 1000000007.

Input data

The first line of the input file contains an integer s (0s31). 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