Long-Awaited Party

CPU usage time limit is 3 seconds

Runtime memory usage limit is 256 megabytes

Sakurako is organizing a party for his friends after their Math test. He has $n$ friends in total. The mood of the $i$ -th friend is represented by an integer $a_{i}$ , and Sakurako's mood is zero.

The mood of the party at any moment is calculated as the bitwise XOR of the mood levels of all friends who have already arrived. Friends arrive at the party one by one, and no two friends arrive at the same time. For any specific order of arrival, Sakurako can calculate the total sum of the party's mood at each step.

For example, if Sakurako has three friends with moods $a_{1}, a_{2}, a_{3}$ respectively and they come to the party in the order $[3, 1, 2]$ , then the sum of moods at each step is $a_{3} + (a_{3} \oplus a_{1}) + (a_{3} \oplus a_{1} \oplus a_{2})$ .

However, since Sakurako doesn't know the exact order in which his friends will arrive, he wants to know the total sum of moods for all possible permutations of their arrival order.

Formally, Sakurako wants to calculate:

p \in S_{n} \sum k = 1 \sum n (a [p_{1}] \oplus a [p_{2}] \oplus \dots \oplus a [p_{k}])

where $S_{n}$ is a group of all permutations of length $n$ .

Additionally, Sakurako sometimes gets curious about specific segments of his friends. He wants to know the total sum of moods if only friends with moods $a_{l}, a_{l + 1}, \dots, a_{r}$ arrive at the party. He has $q$ such questions and asks you to answer them.

Since that sum may be too large, find it modulo $1 0^{9} + 7$ .

Input

The first line contains two integers $n, q (1 \leq n, q \leq 2 \cdot 1 0^{5})$ — the number of friends and the number of questions.

The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n} (0 \leq a_{i} < 2^{30})$ — moods of Sakurako's friends.

Each of the next $q$ lines contains two integers $l, r (1 \leq l \leq r \leq n)$ describing the question.

Output

For each question, output the answer modulo $1 0^{9} + 7$ .

Examples

Input

Answer

Input #1

Answer #1

Note

In the first sample test, all the friends come to the party. There are $6$ possible orderings of their arrival:

$[1, 2, 3]$ : the sum of moods at each step is $4 + (4 \oplus 7) + (4 \oplus 7 \oplus 1) = 9$ ;
$[1, 3, 2]$ : the sum of moods at each step is $4 + (4 \oplus 1) + (4 \oplus 1 \oplus 7) = 11$ ;
$[2, 1, 3]$ : the sum of moods is $7 + (7 \oplus 4) + (7 \oplus 4 \oplus 1) = 12$ ;
$[2, 3, 1]$ : the sum of moods is $7 + (7 \oplus 1) + (7 \oplus 1 \oplus 4) = 15$ ;
$[3, 1, 2]$ : the sum of moods is $1 + (1 \oplus 4) + (1 \oplus 4 \oplus 7) = 8$ ;
$[3, 2, 1]$ : the sum of moods is $1 + (1 \oplus 7) + (1 \oplus 7 \oplus 4) = 9$ .

Hence, the total sum of moods is $9 + 11 + 12 + 15 + 8 + 9 = 64$ .

Scoring

( $15$ points): $n \leq 10, q = 1$ ;
( $56$ points): $a_{1} = a_{2} = \dots = a_{n}$ ;
( $113$ points): $a_{i} \in {0, 1}, n \leq 1000, q = 1$ ;
( $47$ points): $n \leq 1000, q = 1$ ;
( $74$ points): $n \cdot q \leq 5 \cdot 1 0^{5}$ ;
( $43$ points): $a_{i} \in {0, 1}$ ;
( $52$ points): without additional restrictions.

Submissions 15

Acceptance rate 27%