Долгожданная вечеринка

Ограничение времени процессора 3 секунды

Ограничение по использованию памяти 256 мегабайт

Сакурако организует вечеринку для своих друзей после их экзамена по математике. У него всего $n$ друзей. Настроение $i$ -го друга представлено целым числом $a_{i}$ , а настроение Сакурако равно нулю.

Настроение вечеринки в любой момент времени рассчитывается как побитовая XOR настроений всех друзей, которые уже пришли. Друзья приходят на вечеринку по одному, и никто не приходит одновременно. Для любого конкретного порядка прихода Сакурако может вычислить общую сумму настроения вечеринки на каждом этапе.

Например, если у Сакурако есть три друга с настроениями $a_{1}, a_{2}, a_{3}$ соответственно, и они приходят на вечеринку в порядке $[3, 1, 2]$ , то сумма настроений на каждом этапе будет равна $a_{3} + (a_{3} \oplus a_{1}) + (a_{3} \oplus a_{1} \oplus a_{2})$ .

Однако, поскольку Сакурако не знает точный порядок, в котором его друзья придут, он хочет узнать общую сумму настроений для всех возможных перестановок их порядка прихода.

Формально, Сакурако хочет вычислить:

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

где $S_{n}$ — это группа всех перестановок длины $n$ .

Кроме того, Сакурако иногда интересуется конкретными сегментами своих друзей. Он хочет знать общую сумму настроений, если на вечеринку приходят только друзья с настроениями $a_{l}, a_{l + 1}, \dots, a_{r}$ . У него есть $q$ таких вопросов, и он просит вас ответить на них.

Поскольку эта сумма может быть слишком большой, найдите её по модулю $1 0^{9} + 7$ .

Входные данные

Первая строка содержит два целых числа $n, q (1 \leq n, q \leq 2 \cdot 1 0^{5})$ — количество друзей и количество вопросов.

Вторая строка содержит $n$ целых чисел $a_{1}, a_{2}, \dots, a_{n} (0 \leq a_{i} < 2^{30})$ — настроения друзей Сакурако.

Каждая из следующих $q$ строк содержит два целых числа $l, r (1 \leq l \leq r \leq n)$ , описывающих вопрос.

Выходные данные

Для каждого вопроса выведите ответ по модулю $1 0^{9} + 7$ .

Примеры

Ввод #0

Ответ #0

Ввод #1

Ответ #1

Примечание

В первом тестовом примере все друзья приходят на вечеринку. Существует $6$ возможных порядков их прихода:

$[1, 2, 3]$ : сумма настроений на каждом этапе равна $4 + (4 \oplus 7) + (4 \oplus 7 \oplus 1) = 9$ ;
$[1, 3, 2]$ : сумма настроений на каждом этапе равна $4 + (4 \oplus 1) + (4 \oplus 1 \oplus 7) = 11$ ;
$[2, 1, 3]$ : сумма настроений равна $7 + (7 \oplus 4) + (7 \oplus 4 \oplus 1) = 12$ ;
$[2, 3, 1]$ : сумма настроений равна $7 + (7 \oplus 1) + (7 \oplus 1 \oplus 4) = 15$ ;
$[3, 1, 2]$ : сумма настроений равна $1 + (1 \oplus 4) + (1 \oplus 4 \oplus 7) = 8$ ;
$[3, 2, 1]$ : сумма настроений равна $1 + (1 \oplus 7) + (1 \oplus 7 \oplus 4) = 9$ .

Таким образом, общая сумма настроений равна $9 + 11 + 12 + 15 + 8 + 9 = 64$ .

Оценивание

( $15$ баллов): $n \leq 10, q = 1$ ;
( $56$ баллов): $a_{1} = a_{2} = \dots = a_{n}$ ;
( $113$ баллов): $a_{i} \in {0, 1}, n \leq 1000, q = 1$ ;
( $47$ баллов): $n \leq 1000, q = 1$ ;
( $74$ баллов): $n \cdot q \leq 5 \cdot 1 0^{5}$ ;
( $43$ баллов): $a_{i} \in {0, 1}$ ;
( $52$ балла): без дополнительных ограничений.

Отправки 15

Коэффициент принятия 27 %