On vous donne une suite $a$ de $n$ entiers $a_1,a_2,\ldots,a_n$.

On vous donne également un ensemble $S$ de $q$ mises à jour. Chaque mise à jour est définie par trois nombres $l$, $r$ et $x$. Une mise à jour consiste à appliquer l'opération xor avec le nombre $x$ à tous les nombres du segment $[l,r]$ de la suite $a$. Formellement, pour chaque $l\le i\le r$, on effectue la substitution suivante :

$$a_i:=a_i\oplus x$$

Pour un ensemble de mises à jour $S$, définissons $K(S)$ comme la somme de $sum(i,j)^2$ sur tous les segments possibles de la suite $a$, après avoir appliqué à la suite donnée toutes les mises à jour de $S$ :

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

où $sum(i,j)$ est la somme des éléments du segment $[i,j]$ :

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

Votre tâche est de calculer la somme sur les $2^q$ sous-ensembles de l'ensemble donné de mises à jour $S$. Formellement, si $P$ est l'ensemble de tous les sous-ensembles de l'ensemble $S$ de $q$ mises à jour, vous devez calculer :

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

Entrée

La première ligne de l'entrée contient un entier $n$ ($1\le n\le 1000$), le nombre d'éléments de la suite.

La deuxième ligne contient $n$ entiers $a_1,a_2,\ldots,a_n$, séparés par des espaces ($0\le a_i<128$ pour tout $1\le i\le n$), la suite donnée.

La troisième ligne contient un entier $q$ ($1\le q\le 10^5$), le nombre de mises à jour.

Chacune des $q$ lignes suivantes contient trois entiers $l$, $r$ et $x$, séparés par des espaces ($1\le l\le r\le n$, $0\le x<128$), décrivant les mises à jour.

Sortie

Affichez un entier, la réponse au problème. Comme la réponse peut être très grande, affichez-la modulo $10^9+7$.

Sous-tâches

Ce problème comporte neuf sous-tâches :

1. $1\le n\le 10$, $1\le q\le 10$, $0\le a_i,x<128$ pour tout $1\le i\le n$. Vaut 4 points.
2. $1\le n\le 100$, $1\le q\le 10$, $0\le a_i,x<128$ pour tout $1\le i\le n$. Vaut 5 points.
3. $1\le n\le 100$, $1\le q\le 100000$, $0\le a_i,x<32$ pour tout $1\le i\le n$. Il est garanti que tous les segments de mise à jour ont une longueur de $1$. Vaut 6 points.
4. $1\le n\le 1000$, $1\le q\le 500$, $0\le a_i,x<128$ pour tout $1\le i\le n$. Il est garanti que les segments de mise à jour sont deux à deux disjoints. Vaut 9 points.
5. $1\le n\le 30$, $1\le q\le 20$, $0\le a_i,x<32$ pour tout $1\le i\le n$. Vaut 8 points.
6. $1\le n\le 30$, $1\le q\le 5000$, $0\le a_i,x<32$ pour tout $1\le i\le n$. Vaut 11 points.
7. $1\le n\le 300$, $1\le q\le 300$, $0\le a_i,x<128$ pour tout $1\le i\le n$. Vaut 19 points.
8. $1\le n\le 500$, $1\le q\le 100000$, $0\le a_i,x<128$ pour tout $1\le i\le n$. Vaut 30 points.
9. $1\le n\le 1000$, $1\le q\le 100000$, $0\le a_i,x<128$ pour tout $1\le i\le n$. Vaut 8 points.

Exemples

Entrée 1

2
1 3
1
1 2 2

Sortie 1

52

Entrée 2

5
1 2 3 4 5
0

Sortie 2

1001

Remarque

L'opération xor est le OU exclusif bit à bit.

Dans le premier exemple, il existe $2^1=2$ suites possibles après les mises à jour : en appliquant l'unique opération donnée ou en ne l'appliquant pas. Pour les deux suites, les sommes obtenues valent $26$.

Dans le deuxième exemple, l'ensemble $S$ est vide. L'ensemble de tous ses sous-ensembles contient un unique élément $\varnothing$, l'ensemble vide : il n'y a donc aucune mise à jour et vous devez calculer $K(\varnothing)$ pour la suite $a$ donnée.