Se le da una secuencia ~a~ de ~n~ números enteros ~a_1, a_2, ..., a_n~.

Además, un conjunto ~S~ de ~q~ actualizaciones. Cada actualización está definida por tres números ~l, r~ y ~x~. Una actualización consiste en la operación ~xor~ con el número ~x~ aplicada a todos los números en el segmento ~[l, r]~ de la secuencia ~a~. Formalmente, para cada ~l \leq i \leq r~ se realiza la siguiente sustitución:

$$\displaystyle ~a_i := a_i \oplus x~ $$

Para un conjunto de actualizaciones ~S~, definamos ~K(S)~ como la suma de ~sum(i, j)^2~ sobre todos los segmentos posibles de la secuencia ~a~ después de aplicar todas las actualizaciones del conjunto ~S~ a la secuencia dada:

$$\displaystyle ~K(S) = \sum_{1 \leq i \leq j \leq n} sum(i, j)^2~ $$

donde ~sum(i, j)~ se define como la suma de los elementos del segmento ~[i, j]~:

$$\displaystyle ~sum(i, j) = \sum_{x=i}^{j} a_x~ $$

Su tarea consiste en hallar la suma de todos los ~2^q~ subconjuntos del conjunto dado de actualizaciones ~S~. Formalmente, si ~P~ es el conjunto de todos los subconjuntos del conjunto ~S~ de ~q~ actualizaciones, tiene que encontrar lo siguiente:

$$\displaystyle ~ \sum_{subconjunto \in P} K(subconjunto)~ $$

El XOR bit a bit de enteros no negativos ~A~ y ~B~, ~A \oplus B~ , se define de la siguiente manera:

Cuando ~A \oplus B~ se escribe en base dos, el dígito en el lugar de ~2^k~ ~(k \geq 0)~ es ~1~ si exactamente uno de los dígitos en ese lugar de ~A~ y ~B~ es ~1~, y ~0~ en el caso contrario. Por ejemplo, tenemos ~3\oplus 5 = 6~ (en base dos: ~011 \oplus 101 = 110~). Generalmente, el XOR bit a bit de ~k~ enteros no negativos ~p_1,p_2,p_3, \dots ,p_k~ se define como ~(\dots ((p_1 \oplus p_2)\oplus p_3)\oplus \cdots \oplus p_k)~. Podemos demostrar que este valor no depende del orden de ~p_1,p_2,p_3,\dots ,p_k~. Esta operación se hace mediante el símbolo ^ en muchos lenguajes de programación.

Subtareas

• Subtarea 1 (4 puntos): ~1 \leq n \leq 10, \; 1 \leq q \leq 10, \; 0 \leq a_i, \; x < 128~, para todo ~1 \leq i \leq n~.
• Subtarea 2 (5 puntos): ~1 \leq n \leq 100, \; 1 \leq q \leq 10, \; 0 \leq a_i, \; x < 128~, para todo ~1 \leq i \leq n~.
• Subtarea 3 (6 puntos): ~1 \leq n \leq 100, \; 1 \leq q \leq 10^5, \; 0 \leq a_i, \; x < 32~, para todo ~1 \leq i \leq n~, se garantiza que la longitud de todos los segmentos de actualización es igual a ~1~.
• Subtarea 4 (9 puntos): ~1 \leq n \leq 1000, \; 1 \leq q \leq 500, \; 0 \leq a_i, \; x < 128~, para todo ~1 \leq i \leq n~, se garantiza que todos los segmentos de actualización no se cruzan por pares.
• Subtarea 5 (8 puntos): ~1 \leq n \leq 30, \; 1 \leq q \leq 20, \; 0 \leq a_i, \; x < 32~, para todo ~1 \leq i \leq n~.
• Subtarea 6 (11 puntos): ~1 \leq n \leq 30, \; 1 \leq q \leq 5000, \; 0 \leq a_i, \; x < 32~, para todo ~1 \leq i \leq n~.
• Subtarea 7 (19 puntos): ~1 \leq n \leq 300, \; 1 \leq q \leq 300, \; 0 \leq a_i, \; x < 128~, para todo ~1 \leq i \leq n~.
• Subtarea 8 (30 puntos): ~1 \leq n \leq 500, \; 1 \leq q \leq 10^5, \; 0 \leq a_i, \; x < 128~, para todo ~1 \leq i \leq n~.
• Subtarea 9 (8 puntos): Sin restricciones adicionales.

Entrada

La primera línea de entrada contiene un único número entero ~n~ ~(1 \leq n \leq 1000) \; -~ el número de elementos de la secuencia.

La segunda línea contiene ~n~ números enteros separados por espacios ~a_1, a_2, ..., a_n~ ~(0 \leq a_i < 128~ para cada ~1 \leq i \leq n) \; -~ la secuencia dada.

La tercera línea contiene un único entero ~q~ ~(1 \leq q \leq 10^5) \; -~ el número de actualizaciones.

Cada una de las siguientes ~q~ líneas contiene tres números enteros separados por espacios ~l, r~ y ~x~ ~(1 \leq l \leq r \leq n, \; 0 \leq x < 128) \; -~ descripciones de las actualizaciones.

Salida

Imprima un entero único: la respuesta al problema. Si es muy grande, imprímala módulo ~10^9 + 7~.

Ejemplos

Entrada 1

2
1 3
1
1 2 2

Salida 1

52

Hay ~2^1 = 2~ secuencias posibles después de aplicar las actualizaciones ~-~ cuando se aplica la única operación dada y cuando no. En ambas secuencias las sumas resultantes son iguales a ~26~.

Entrada 2

5
1 2 3 4 5
0

Salida 2

1001

El conjunto ~S~ está vacío, el conjunto de todos los subconjuntos consta de un único elemento ~\emptyset \; -~ el conjunto vacío, es decir, no hay actualizaciones y se debe encontrar ~K(\emptyset)~ para la secuencia dada ~a~.