Gegeben ist eine Folge $a$ aus $n$ ganzen Zahlen $a_1,a_2,\ldots,a_n$.

Außerdem ist eine Menge $S$ aus $q$ Aktualisierungen gegeben. Jede Aktualisierung ist durch drei Zahlen $l,r,x$ definiert. Bei einer Aktualisierung wird die XOR-Operation mit der Zahl $x$ auf alle Zahlen im Abschnitt $[l,r]$ der Folge $a$ angewendet. Formal wird für jedes $l\le i\le r$ folgende Ersetzung vorgenommen:

$$a_i:=a_i\oplus x.$$

Für eine Menge von Aktualisierungen $S$ definieren wir $K(S)$ als die Summe von $sum(i,j)^2$ über alle möglichen Abschnitte der Folge $a$, nachdem alle Aktualisierungen aus $S$ auf die gegebene Folge angewendet wurden:

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

wobei $sum(i,j)$ als die Summe der Elemente im Abschnitt $[i,j]$ definiert ist:

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

Deine Aufgabe ist es, die Summe über alle $2^q$ Teilmengen der gegebenen Aktualisierungsmenge $S$ zu finden. Ist $P$ die Menge aller Teilmengen von $S$, das $q$ Aktualisierungen enthält, musst du formal Folgendes berechnen:

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

Eingabe

Die erste Eingabezeile enthält eine ganze Zahl $n$ ($1\le n\le1000$) — die Anzahl der Elemente der Folge.

Die zweite Zeile enthält $n$ durch Leerzeichen getrennte ganze Zahlen $a_1,a_2,\ldots,a_n$ ($0\le a_i<128$ für jedes $1\le i\le n$) — die gegebene Folge.

Die dritte Zeile enthält eine ganze Zahl $q$ ($1\le q\le10^5$) — die Anzahl der Aktualisierungen.

Jede der nächsten $q$ Zeilen enthält drei durch Leerzeichen getrennte ganze Zahlen $l,r,x$ ($1\le l\le r\le n$, $0\le x<128$) — die Beschreibungen der Aktualisierungen.

Ausgabe

Gib eine ganze Zahl aus — die Antwort auf die Aufgabe. Da die Antwort sehr groß sein kann, gib sie modulo $10^9+7$ aus.

Teilaufgaben

Diese Aufgabe besteht aus neun Teilaufgaben:

1. $1\le n\le10$, $1\le q\le10$, $0\le a_i,x<128$ für alle $1\le i\le n$. 4 Punkte.
2. $1\le n\le100$, $1\le q\le10$, $0\le a_i,x<128$ für alle $1\le i\le n$. 5 Punkte.
3. $1\le n\le100$, $1\le q\le100000$, $0\le a_i,x<32$ für alle $1\le i\le n$. Es ist garantiert, dass alle Aktualisierungsabschnitte die Länge $1$ haben. 6 Punkte.
4. $1\le n\le1000$, $1\le q\le500$, $0\le a_i,x<128$ für alle $1\le i\le n$. Es ist garantiert, dass die Aktualisierungsabschnitte sich paarweise nicht überschneiden. 9 Punkte.
5. $1\le n\le30$, $1\le q\le20$, $0\le a_i,x<32$ für alle $1\le i\le n$. 8 Punkte.
6. $1\le n\le30$, $1\le q\le5000$, $0\le a_i,x<32$ für alle $1\le i\le n$. 11 Punkte.
7. $1\le n\le300$, $1\le q\le300$, $0\le a_i,x<128$ für alle $1\le i\le n$. 19 Punkte.
8. $1\le n\le500$, $1\le q\le100000$, $0\le a_i,x<128$ für alle $1\le i\le n$. 30 Punkte.
9. $1\le n\le1000$, $1\le q\le100000$, $0\le a_i,x<128$ für alle $1\le i\le n$. 8 Punkte.

Beispiele

Eingabe 1

2
1 3
1
1 2 2

Ausgabe 1

52

Eingabe 2

5
1 2 3 4 5
0

Ausgabe 2

1001

Hinweis

Die XOR-Operation ist das bitweise exklusive Oder.

Im ersten Beispiel gibt es nach Anwendung der Aktualisierungen $2^1=2$ mögliche Folgen — mit und ohne Anwendung der einzigen gegebenen Operation. Für beide Folgen ergibt sich die Summe $26$.

Im zweiten Beispiel ist die Menge $S$ leer. Die Menge aller Teilmengen enthält ein einziges Element $\varnothing$ — die leere Menge. Das heißt, es gibt keine Aktualisierungen und du musst $K(\varnothing)$ für die gegebene Folge $a$ berechnen.