星系間飛船 - Problem

畀定一個由 $n$ 個整數 $a_1,a_2,\ldots,a_n$ 組成嘅序列 $a$。

另外，畀定一個包含 $q$ 次修改嘅集合 $S$。每次修改由三個數 $l$、$r$ 同 $x$ 定義。一次修改會將序列 $a$ 嘅區間 $[l,r]$ 入面所有數，同數字 $x$ 做 xor 運算。正式嚟講，對每個 $l \le i \le r$，執行以下替換：

$$a_i:=a_i\oplus x$$

對於修改集合 $S$，定義 $K(S)$ 為將集合 $S$ 嘅所有修改套用到畀定序列之後，對序列 $a$ 所有可能區間嘅 $sum(i,j)^2$ 求和：

$$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$ 個子集求總和。正式嚟講，設 $P$ 係包含 $q$ 次修改嘅集合 $S$ 嘅所有子集所組成嘅集合，你要求出：

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

輸入第一行包含一個整數 $n$（$1 \le n \le 1000$），表示序列嘅元素數量。

第二行包含 $n$ 個以空格分隔嘅整數 $a_1,a_2,\ldots,a_n$（對每個 $1 \le i \le n$，$0 \le a_i < 128$），表示畀定嘅序列。

第三行包含一個整數 $q$（$1 \le q \le 10^5$），表示修改次數。

之後 $q$ 行，每行包含三個以空格分隔嘅整數 $l$、$r$ 同 $x$（$1 \le l \le r \le n$，$0 \le x < 128$），描述一次修改。

輸出一個整數，表示題目嘅答案。由於答案可能非常大，請輸出佢對 $10^9+7$ 取模嘅結果。

呢道題目有九個子任務：

$1 \le n \le 10$，$1 \le q \le 10$，對所有 $1 \le i \le n$，$0 \le a_i,x < 128$。4 分。
$1 \le n \le 100$，$1 \le q \le 10$，對所有 $1 \le i \le n$，$0 \le a_i,x < 128$。5 分。
$1 \le n \le 100$，$1 \le q \le 100000$，對所有 $1 \le i \le n$，$0 \le a_i,x < 32$。保證所有修改區間嘅長度都等於 $1$。6 分。
$1 \le n \le 1000$，$1 \le q \le 500$，對所有 $1 \le i \le n$，$0 \le a_i,x < 128$。保證所有修改區間兩兩冇交集。9 分。
$1 \le n \le 30$，$1 \le q \le 20$，對所有 $1 \le i \le n$，$0 \le a_i,x < 32$。8 分。
$1 \le n \le 30$，$1 \le q \le 5000$，對所有 $1 \le i \le n$，$0 \le a_i,x < 32$。11 分。
$1 \le n \le 300$，$1 \le q \le 300$，對所有 $1 \le i \le n$，$0 \le a_i,x < 128$。19 分。
$1 \le n \le 500$，$1 \le q \le 100000$，對所有 $1 \le i \le n$，$0 \le a_i,x < 128$。30 分。
$1 \le n \le 1000$，$1 \le q \le 100000$，對所有 $1 \le i \le n$，$0 \le a_i,x < 128$。8 分。

5
1 2 3 4 5
0

xor 運算即係逐位異或。

第一個樣例中，套用修改之後有 $2^1=2$ 個可能嘅序列：執行唯一嗰次修改，或者唔執行。兩個序列得出嘅總和都等於 $26$。

第二個樣例中，集合 $S$ 係空集，所有子集組成嘅集合只有一個元素 $\varnothing$，即空集。亦即係冇任何修改，你要求出畀定序列 $a$ 嘅 $K(\varnothing)$。

QOJ.ac