É-lhe dada uma sequência $a$ de $n$ números inteiros $a_1,a_2,\ldots,a_n$.

Além disso, é-lhe dado um conjunto $S$ de $q$ atualizações. Cada atualização é definida por três números $l$, $r$ e $x$. Uma atualização consiste em aplicar a operação xor com o número $x$ a todos os números do segmento $[l,r]$ da sequência $a$. Formalmente, para cada $l\le i\le r$, realiza-se a seguinte substituição:

$$a_i:=a_i\oplus x$$

Para um conjunto de atualizações $S$, definimos $K(S)$ como a soma de $sum(i,j)^2$ sobre todos os segmentos possíveis da sequência $a$, depois de aplicar todas as atualizações do conjunto $S$ à sequência dada:

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

onde $sum(i,j)$ é definido como a soma dos elementos do segmento $[i,j]$:

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

A sua tarefa é encontrar a soma sobre todos os $2^q$ subconjuntos do conjunto de atualizações $S$ dado. Formalmente, se $P$ é o conjunto de todos os subconjuntos do conjunto $S$ de $q$ atualizações, deve encontrar o seguinte:

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

Entrada

A primeira linha da entrada contém um único inteiro $n$ ($1\le n\le1000$) — o número de elementos da sequência.

A segunda linha contém $n$ números inteiros $a_1,a_2,\ldots,a_n$, separados por espaços ($0\le a_i<128$ para todo $1\le i\le n$) — a sequência dada.

A terceira linha contém um único inteiro $q$ ($1\le q\le10^5$) — o número de atualizações.

Cada uma das $q$ linhas seguintes contém três números inteiros $l$, $r$ e $x$, separados por espaços ($1\le l\le r\le n$, $0\le x<128$) — as descrições das atualizações.

Saída

Imprima um único inteiro — a resposta ao problema. Como a resposta pode ser muito grande, imprima-a módulo $10^9+7$.

Subtarefas

Este problema consiste em nove subtarefas:

1. $1\le n\le10$, $1\le q\le10$, $0\le a_i,x<128$, para todo $1\le i\le n$. 4 pontos.
2. $1\le n\le100$, $1\le q\le10$, $0\le a_i,x<128$, para todo $1\le i\le n$. 5 pontos.
3. $1\le n\le100$, $1\le q\le100000$, $0\le a_i,x<32$, para todo $1\le i\le n$. É garantido que o comprimento de todos os segmentos de atualização é igual a $1$. 6 pontos.
4. $1\le n\le1000$, $1\le q\le500$, $0\le a_i,x<128$, para todo $1\le i\le n$. É garantido que todos os segmentos de atualização são disjuntos dois a dois. 9 pontos.
5. $1\le n\le30$, $1\le q\le20$, $0\le a_i,x<32$, para todo $1\le i\le n$. 8 pontos.
6. $1\le n\le30$, $1\le q\le5000$, $0\le a_i,x<32$, para todo $1\le i\le n$. 11 pontos.
7. $1\le n\le300$, $1\le q\le300$, $0\le a_i,x<128$, para todo $1\le i\le n$. 19 pontos.
8. $1\le n\le500$, $1\le q\le100000$, $0\le a_i,x<128$, para todo $1\le i\le n$. 30 pontos.
9. $1\le n\le1000$, $1\le q\le100000$, $0\le a_i,x<128$, para todo $1\le i\le n$. 8 pontos.

Exemplos

Entrada 1

2
1 3
1
1 2 2

Saída 1

52

Entrada 2

5
1 2 3 4 5
0

Saída 2

1001

Nota

A operação xor é o OU exclusivo bit a bit.

No primeiro exemplo, existem $2^1=2$ sequências possíveis após aplicar as atualizações: aplicando a única operação dada e não a aplicando. Em ambas as sequências, as somas resultantes são iguais a $26$.

No segundo exemplo, o conjunto $S$ é vazio; o conjunto de todos os subconjuntos consiste num único elemento $\varnothing$ — o conjunto vazio. Ou seja, não há atualizações e tem de encontrar $K(\varnothing)$ para a sequência $a$ dada.