Dany jest ciąg $a$ złożony z $n$ liczb całkowitych $a_1,a_2,\ldots,a_n$.

Ponadto dany jest zbiór $S$ zawierający $q$ aktualizacji. Każdą aktualizację określają trzy liczby $l$, $r$ i $x$. Aktualizacja polega na wykonaniu operacji xor z liczbą $x$ na wszystkich liczbach na przedziale $[l,r]$ ciągu $a$. Formalnie, dla każdego $l\le i\le r$ wykonujemy podstawienie:

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

Dla zbioru aktualizacji $S$ zdefiniujmy $K(S)$ jako sumę wartości $sum(i,j)^2$ po wszystkich możliwych przedziałach ciągu $a$ po zastosowaniu do danego ciągu wszystkich aktualizacji ze zbioru $S$:

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

gdzie $sum(i,j)$ oznacza sumę elementów na przedziale $[i,j]$:

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

Twoim zadaniem jest obliczenie sumy po wszystkich $2^q$ podzbiorach danego zbioru aktualizacji $S$. Formalnie, jeśli $P$ jest zbiorem wszystkich podzbiorów zbioru $S$ zawierającego $q$ aktualizacji, należy obliczyć:

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

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $n$ $(1\le n\le1000)$ — liczbę elementów ciągu.

Drugi wiersz zawiera $n$ liczb całkowitych $a_1,a_2,\ldots,a_n$ oddzielonych spacjami ($0\le a_i<128$ dla każdego $1\le i\le n$) — dany ciąg.

Trzeci wiersz zawiera jedną liczbę całkowitą $q$ $(1\le q\le10^5)$ — liczbę aktualizacji.

Każdy z kolejnych $q$ wierszy zawiera trzy liczby całkowite $l$, $r$ i $x$ oddzielone spacjami $(1\le l\le r\le n,\ 0\le x<128)$ — opis aktualizacji.

Wyjście

Wypisz jedną liczbę całkowitą — odpowiedź na zadanie. Ponieważ odpowiedź może być bardzo duża, wypisz ją modulo $10^9+7$.

Podzadania

To zadanie składa się z dziewięciu podzadań:

1. $1\le n\le10,\ 1\le q\le10,\ 0\le a_i,x<128$ dla każdego $1\le i\le n$. Warte 4 punkty.

2. $1\le n\le100,\ 1\le q\le10,\ 0\le a_i,x<128$ dla każdego $1\le i\le n$. Warte 5 punktów.

3. $1\le n\le100,\ 1\le q\le100000,\ 0\le a_i,x<32$ dla każdego $1\le i\le n$. Gwarantuje się, że długość przedziału każdej aktualizacji wynosi $1$. Warte 6 punktów.

4. $1\le n\le1000,\ 1\le q\le500,\ 0\le a_i,x<128$ dla każdego $1\le i\le n$. Gwarantuje się, że przedziały wszystkich aktualizacji są parami rozłączne. Warte 9 punktów.

5. $1\le n\le30,\ 1\le q\le20,\ 0\le a_i,x<32$ dla każdego $1\le i\le n$. Warte 8 punktów.

6. $1\le n\le30,\ 1\le q\le5000,\ 0\le a_i,x<32$ dla każdego $1\le i\le n$. Warte 11 punktów.

7. $1\le n\le300,\ 1\le q\le300,\ 0\le a_i,x<128$ dla każdego $1\le i\le n$. Warte 19 punktów.

8. $1\le n\le500,\ 1\le q\le100000,\ 0\le a_i,x<128$ dla każdego $1\le i\le n$. Warte 30 punktów.

9. $1\le n\le1000,\ 1\le q\le100000,\ 0\le a_i,x<128$ dla każdego $1\le i\le n$. Warte 8 punktów.

Przykład

Wejście 1

2
1 3
1
1 2 2

Wyjście 1

52

Wejście 2

5
1 2 3 4 5
0

Wyjście 2

1001

Uwagi

Operacja xor to bitowa alternatywa wykluczająca.

W pierwszym przykładzie istnieją $2^1=2$ możliwe ciągi po zastosowaniu aktualizacji — z wykonaniem jedynej podanej operacji i bez jej wykonania. Dla obu ciągów otrzymane sumy wynoszą $26$.

W drugim przykładzie zbiór $S$ jest pusty, a zbiór wszystkich podzbiorów zawiera jeden element $\varnothing$ — zbiór pusty. Oznacza to, że nie ma aktualizacji i należy obliczyć $K(\varnothing)$ dla danego ciągu $a$.