U-turn bits
Let n = 2^s, where s ≥ 0 — 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
The first line of the input file contains an integer s (0 ≤ s ≤ 31). 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).
Output
The output file output k numbers - the answers to these requests.