Fiesta Esperada#11715
Sakurako está organizando una fiesta para sus amigos después de su examen de Matemáticas. Tiene un total de amigos. El estado de ánimo del -ésimo amigo está representado por un entero a_i, y el estado de ánimo de Sakurako es cero.
El estado de ánimo de la fiesta en cualquier momento se calcula como el XOR a nivel de bits de los niveles de ánimo de todos los amigos que ya han llegado. Los amigos llegan a la fiesta uno por uno, y no hay dos amigos que lleguen al mismo tiempo. Para cualquier orden específico de llegada, Sakurako puede calcular la suma total del estado de ánimo de la fiesta en cada paso.
Por ejemplo, si Sakurako tiene tres amigos con estados de ánimo a_1,~a_2,~a_3 respectivamente y llegan a la fiesta en el orden [3,~1,~2], entonces la suma de los estados de ánimo en cada paso es a_3+(a_3\oplus a_1)+(a_3\oplus a_1\oplus a_2).
Sin embargo, dado que Sakurako no sabe el orden exacto en el que llegarán sus amigos, quiere saber la suma total de los estados de ánimo para todas las permutaciones posibles de su orden de llegada.
Formalmente, Sakurako quiere calcular:
donde \mathcal{S_n} es un grupo de todas las permutaciones de longitud .
Además, a veces Sakurako se siente curioso acerca de segmentos específicos de sus amigos. Quiere saber la suma total de los estados de ánimo si solo llegan amigos con estados de ánimo a_l, a_{l+1},\dots, a_r a la fiesta. Tiene tales preguntas y te pide que las respondas.
Dado que esa suma puede ser demasiado grande, encuéntrala módulo 10^9+7.
La primera línea contiene dos enteros n,q ~(1\le n,q \le 2\cdot 10^5) — el número de amigos y el número de preguntas.
La segunda línea contiene enteros a_1,a_2,\dots,a_n ~(0\le a_i < 2^{30}) — estados de ánimo de los amigos de Sakurako.
Cada una de las siguientes líneas contiene dos enteros l, r ~(1\le l\le r\le n) que describen la pregunta.
Para cada pregunta, imprime la respuesta módulo 10^9+7.
Ejemplo
Ejemplo 1
En la primera prueba de muestra, todos los amigos llegan a la fiesta. Hay ordenamientos posibles de su llegada:
[1, ~2, ~3]: la suma de los estados de ánimo en cada paso es 4 + (4\oplus 7) + (4\oplus7\oplus 1)=9;
[1, ~3, ~2]: la suma de los estados de ánimo en cada paso es 4+(4\oplus1)+(4\oplus1\oplus7)=11;
[2, ~1, ~3]: la suma de los estados de ánimo es 7 + (7\oplus 4) + (7\oplus4\oplus1)=12;
[2, ~3, ~1]: la suma de los estados de ánimo es 7 + (7\oplus 1) + (7\oplus1\oplus4)=15;
[3, ~1, ~2]: la suma de los estados de ánimo es 1+(1\oplus 4)+(1\oplus4\oplus7)=8;
[3, ~2, ~1]: la suma de los estados de ánimo es 1+(1\oplus 7)+(1\oplus7\oplus4)=9.
Por lo tanto, la suma total de los estados de ánimo es 9+11+12+15+8+9=64.
( puntos): n\le 10, ~q=1;
( puntos): a_1=a_2=\dots=a_n;
( puntos): a_i\in\{0,~1\}, ~n\le 1000, ~q=1;
( puntos): n\le 1000, ~q=1;
( puntos): n\cdot q\le 5\cdot 10^5;
( puntos): a_i\in\{0,~1\};
( puntos): sin restricciones adicionales.