Anda diberikan sebuah barisan $a$ yang terdiri dari $n$ bilangan bulat $a_1,a_2,\ldots,a_n$.

Selain itu, Anda diberikan sebuah himpunan $S$ yang berisi $q$ pembaruan. Setiap pembaruan ditentukan oleh tiga bilangan $l$, $r$, dan $x$. Sebuah pembaruan menerapkan operasi xor dengan bilangan $x$ pada semua bilangan di segmen $[l,r]$ dari barisan $a$. Secara formal, untuk setiap $l\le i\le r$, penggantian berikut dilakukan:

$$a_i:=a_i\oplus x$$

Untuk suatu himpunan pembaruan $S$, definisikan $K(S)$ sebagai jumlah $sum(i,j)^2$ untuk seluruh segmen yang mungkin dari barisan $a$ setelah semua pembaruan dalam himpunan $S$ diterapkan pada barisan yang diberikan:

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

dengan $sum(i,j)$ didefinisikan sebagai jumlah elemen pada segmen $[i,j]$:

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

Tugas Anda adalah mencari jumlah untuk seluruh $2^q$ himpunan bagian dari himpunan pembaruan $S$ yang diberikan. Secara formal, jika $P$ adalah himpunan seluruh himpunan bagian dari himpunan $S$ yang berisi $q$ pembaruan, Anda harus mencari:

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

Masukan

Baris pertama masukan berisi satu bilangan bulat $n$ ($1\le n\le1000$) — banyaknya elemen dalam barisan.

Baris kedua berisi $n$ bilangan bulat $a_1,a_2,\ldots,a_n$ yang dipisahkan oleh spasi ($0\le a_i<128$ untuk setiap $1\le i\le n$) — barisan yang diberikan.

Baris ketiga berisi satu bilangan bulat $q$ ($1\le q\le10^5$) — banyaknya pembaruan.

Masing-masing dari $q$ baris berikutnya berisi tiga bilangan bulat $l$, $r$, dan $x$ yang dipisahkan oleh spasi ($1\le l\le r\le n$, $0\le x<128$) — deskripsi pembaruan.

Keluaran

Cetak satu bilangan bulat — jawaban untuk masalah ini. Karena jawabannya dapat sangat besar, cetak nilainya modulo $10^9+7$.

Subtugas

Masalah ini terdiri dari sembilan subtugas:

1. $1\le n\le10$, $1\le q\le10$, $0\le a_i,x<128$ untuk semua $1\le i\le n$. Bernilai 4 poin.
2. $1\le n\le100$, $1\le q\le10$, $0\le a_i,x<128$ untuk semua $1\le i\le n$. Bernilai 5 poin.
3. $1\le n\le100$, $1\le q\le100000$, $0\le a_i,x<32$ untuk semua $1\le i\le n$. Dijamin bahwa panjang semua segmen pembaruan sama dengan $1$. Bernilai 6 poin.
4. $1\le n\le1000$, $1\le q\le500$, $0\le a_i,x<128$ untuk semua $1\le i\le n$. Dijamin bahwa setiap pasangan segmen pembaruan tidak beririsan. Bernilai 9 poin.
5. $1\le n\le30$, $1\le q\le20$, $0\le a_i,x<32$ untuk semua $1\le i\le n$. Bernilai 8 poin.
6. $1\le n\le30$, $1\le q\le5000$, $0\le a_i,x<32$ untuk semua $1\le i\le n$. Bernilai 11 poin.
7. $1\le n\le300$, $1\le q\le300$, $0\le a_i,x<128$ untuk semua $1\le i\le n$. Bernilai 19 poin.
8. $1\le n\le500$, $1\le q\le100000$, $0\le a_i,x<128$ untuk semua $1\le i\le n$. Bernilai 30 poin.
9. $1\le n\le1000$, $1\le q\le100000$, $0\le a_i,x<128$ untuk semua $1\le i\le n$. Bernilai 8 poin.

Contoh

Masukan 1

2
1 3
1
1 2 2

Keluaran 1

52

Masukan 2

5
1 2 3 4 5
0

Keluaran 2

1001

Catatan

Operasi xor adalah operasi OR eksklusif per bit.

Pada contoh pertama, ada $2^1=2$ kemungkinan barisan setelah menerapkan pembaruan — dengan menerapkan satu-satunya operasi yang diberikan atau tanpa menerapkannya. Untuk kedua barisan, jumlah yang dihasilkan sama dengan $26$.

Pada contoh kedua, himpunan $S$ kosong, dan himpunan seluruh himpunan bagiannya terdiri dari satu elemen $\varnothing$ — himpunan kosong, yaitu tidak ada pembaruan dan Anda harus mencari $K(\varnothing)$ untuk barisan $a$ yang diberikan.