Se te da una secuencia $a$ de $n$ números enteros $a_1,a_2,\ldots,a_n$.

Además, se te da un conjunto $S$ de $q$ actualizaciones. Cada actualización se define mediante tres números $l$, $r$ y $x$. Una actualización consiste en aplicar la operación xor con el número $x$ a todos los números del segmento $[l,r]$ de la secuencia $a$. Formalmente, para cada $l\le i\le r$, se realiza la siguiente sustitución:

$$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 a la secuencia dada todas las actualizaciones del conjunto $S$:

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

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

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

Tu tarea es encontrar la suma sobre 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, debes encontrar lo siguiente:

$$\sum_{subset\in P}K(subset)$$

Entrada

La primera línea de la entrada contiene un único entero $n$ ($1\le n\le1000$), el número de elementos de la secuencia.

La segunda línea contiene $n$ enteros $a_1,a_2,\ldots,a_n$ separados por espacios ($0\le a_i<128$ para cada $1\le i\le n$), la secuencia dada.

La tercera línea contiene un único entero $q$ ($1\le q\le10^5$), el número de actualizaciones.

Cada una de las siguientes $q$ líneas contiene tres enteros $l$, $r$ y $x$ separados por espacios ($1\le l\le r\le n$, $0\le x<128$), que describen las actualizaciones.

Salida

Imprime un único entero: la respuesta al problema. Como la respuesta puede ser muy grande, imprímela módulo $10^9+7$.

Subtareas

Este problema consta de nueve subtareas:

1. $1\le n\le10$, $1\le q\le10$, $0\le a_i,x<128$ para todo $1\le i\le n$. Vale 4 puntos.
2. $1\le n\le100$, $1\le q\le10$, $0\le a_i,x<128$ para todo $1\le i\le n$. Vale 5 puntos.
3. $1\le n\le100$, $1\le q\le100000$, $0\le a_i,x<32$ para todo $1\le i\le n$. Se garantiza que la longitud de todos los segmentos de actualización es $1$. Vale 6 puntos.
4. $1\le n\le1000$, $1\le q\le500$, $0\le a_i,x<128$ para todo $1\le i\le n$. Se garantiza que los segmentos de actualización no se intersecan dos a dos. Vale 9 puntos.
5. $1\le n\le30$, $1\le q\le20$, $0\le a_i,x<32$ para todo $1\le i\le n$. Vale 8 puntos.
6. $1\le n\le30$, $1\le q\le5000$, $0\le a_i,x<32$ para todo $1\le i\le n$. Vale 11 puntos.
7. $1\le n\le300$, $1\le q\le300$, $0\le a_i,x<128$ para todo $1\le i\le n$. Vale 19 puntos.
8. $1\le n\le500$, $1\le q\le100000$, $0\le a_i,x<128$ para todo $1\le i\le n$. Vale 30 puntos.
9. $1\le n\le1000$, $1\le q\le100000$, $0\le a_i,x<128$ para todo $1\le i\le n$. Vale 8 puntos.

Ejemplos

Entrada 1

2
1 3
1
1 2 2

Salida 1

52

Entrada 2

5
1 2 3 4 5
0

Salida 2

1001

Nota

La operación xor es el OR exclusivo bit a bit.

En el primer ejemplo, hay $2^1=2$ secuencias posibles después de aplicar las actualizaciones: aplicando la única operación dada y sin aplicarla. En ambas secuencias, las sumas resultantes son iguales a $26$.

En el segundo ejemplo, el conjunto $S$ está vacío y el conjunto de todos sus subconjuntos contiene un único elemento $\varnothing$, el conjunto vacío; es decir, no hay actualizaciones y debes encontrar $K(\varnothing)$ para la secuencia $a$ dada.