$n$ 個の整数 $a_1,a_2,\ldots,a_n$ からなる数列 $a$ が与えられます。

さらに、$q$ 個の更新からなる集合 $S$ が与えられます。各更新は 3 つの数 $l,r,x$ で定義されます。更新では、数列 $a$ の区間 $[l,r]$ にあるすべての数に対して、数 $x$ との xor 演算を適用します。形式的には、各 $l\le i\le r$ について、次の代入を行います。

$$a_i:=a_i\oplus x$$

更新の集合 $S$ に対して、与えられた数列に $S$ のすべての更新を適用した後の数列 $a$ のすべての区間にわたる $sum(i,j)^2$ の総和を $K(S)$ と定義します。

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

ここで、$sum(i,j)$ は区間 $[i,j]$ の要素の総和として定義されます。

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

与えられた更新の集合 $S$ の $2^q$ 個の部分集合すべてにわたる総和を求めてください。形式的には、$q$ 個の更新からなる集合 $S$ のすべての部分集合の集合を $P$ としたとき、次の値を求める必要があります。

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

入力

入力の 1 行目には、数列の要素数を表す整数 $n$ ($1\le n\le1000$) が与えられます。

2 行目には、与えられた数列を表す $n$ 個の整数 $a_1,a_2,\ldots,a_n$（各 $1\le i\le n$ について $0\le a_i<128$）が空白区切りで与えられます。

3 行目には、更新の個数を表す整数 $q$ ($1\le q\le10^5$) が与えられます。

続く $q$ 行の各行には、更新を表す 3 つの整数 $l,r,x$ ($1\le l\le r\le n$, $0\le x<128$) が空白区切りで与えられます。

出力

この問題の答えを表す整数を 1 つ出力してください。答えは非常に大きくなる可能性があるため、$10^9+7$ で割った余りを出力してください。

小課題

この問題は 9 つの小課題からなります。

1. $1\le n\le10$, $1\le q\le10$, すべての $1\le i\le n$ について $0\le a_i,x<128$。4 点。
2. $1\le n\le100$, $1\le q\le10$, すべての $1\le i\le n$ について $0\le a_i,x<128$。5 点。
3. $1\le n\le100$, $1\le q\le100000$, すべての $1\le i\le n$ について $0\le a_i,x<32$。すべての更新区間の長さが $1$ であることが保証されます。6 点。
4. $1\le n\le1000$, $1\le q\le500$, すべての $1\le i\le n$ について $0\le a_i,x<128$。どの 2 つの更新区間も交わらないことが保証されます。9 点。
5. $1\le n\le30$, $1\le q\le20$, すべての $1\le i\le n$ について $0\le a_i,x<32$。8 点。
6. $1\le n\le30$, $1\le q\le5000$, すべての $1\le i\le n$ について $0\le a_i,x<32$。11 点。
7. $1\le n\le300$, $1\le q\le300$, すべての $1\le i\le n$ について $0\le a_i,x<128$。19 点。
8. $1\le n\le500$, $1\le q\le100000$, すべての $1\le i\le n$ について $0\le a_i,x<128$。30 点。
9. $1\le n\le1000$, $1\le q\le100000$, すべての $1\le i\le n$ について $0\le a_i,x<128$。8 点。

入出力例

入力 1

2
1 3
1
1 2 2

出力 1

52

入力 2

5
1 2 3 4 5
0

出力 2

1001

注記

xor 演算はビットごとの排他的論理和です。

最初の例では、更新を適用した後の数列として、与えられた唯一の操作を適用する場合と適用しない場合の $2^1=2$ 通りが考えられます。どちらの数列でも、得られる総和は $26$ です。

2 つ目の例では、集合 $S$ は空であり、すべての部分集合の集合は空集合 $\varnothing$ という 1 つの要素からなります。つまり、更新はなく、与えられた数列 $a$ に対する $K(\varnothing)$ を求める必要があります。