Bit Rotation 2
Let n = 2^s, where s is a non-negative integer. For each integer i ranging from 0 to n-1, define the value a_i as follows: Consider the binary representation of the number i as b_{s-1}...b_1b_0, padded with leading zeros to ensure it has a length of s. Reverse these bits to get b_0b_1...b_{s-1}. The value of a_i is then the integer whose binary representation is b_0b_1...b_{s-1}.
For instance, if s = 3 and i = 3, the binary representation is 011_2. Reversing this gives 110_2, so for s = 3, a_3 = 6.
Your task is to efficiently answer queries about the sum a_l + a_{l+1} + ... + a_r modulo 1000000007 for a given s.
Input
The first line of the input contains an integer s (0 ≤ s ≤ 25). The second line contains an integer k, the number of queries (1 ≤ k ≤ 5·10^5). The following k lines each contain a pair of integers l, r (0 ≤ l ≤ r < 2^s).
Output
Output k numbers, each representing the answer to a respective query.