给定一个包含 $n$ 个整数的序列 $a_1, a_2, \dots, a_n$。 此外，给定一个包含 $q$ 个更新操作的集合 $S$。每个更新由三个数 $l, r$ 和 $x$ 定义。一个更新操作是指将序列 $a$ 中区间 $[l, r]$ 内的所有数字与 $x$ 进行异或运算。形式化地，对于每个 $l \le i \le r$，执行以下替换： $a_i := a_i \oplus x$

对于一个更新集合 $S$，定义 $K(S)$ 为在对给定序列 $a$ 应用集合 $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$$

你的任务是求出所有 $2^q$ 个更新集合 $S$ 的子集的 $K(subset)$ 之和。形式化地，如果 $P$ 是 $q$ 个更新集合 $S$ 的所有子集构成的集合，你需要求出： $$\sum_{subset \in P} K(subset)$$

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 1000$)，表示序列中元素的个数。 第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i < 128$，对于每个 $1 \le i \le n$)，表示给定的序列。 第三行包含一个整数 $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. $1 \le n \le 10, 1 \le q \le 10, 0 \le a_i, x < 128$，对于所有 $1 \le i \le n$。分值 4 分。
2. $1 \le n \le 100, 1 \le q \le 10, 0 \le a_i, x < 128$，对于所有 $1 \le i \le n$。分值 5 分。
3. $1 \le n \le 100, 1 \le q \le 100000, 0 \le a_i, x < 32$，对于所有 $1 \le i \le n$。保证所有更新区间的长度均为 1。分值 6 分。
4. $1 \le n \le 1000, 1 \le q \le 500, 0 \le a_i, x < 128$，对于所有 $1 \le i \le n$。保证所有更新区间两两不相交。分值 9 分。
5. $1 \le n \le 30, 1 \le q \le 20, 0 \le a_i, x < 32$，对于所有 $1 \le i \le n$。分值 8 分。
6. $1 \le n \le 30, 1 \le q \le 5000, 0 \le a_i, x < 32$，对于所有 $1 \le i \le n$。分值 11 分。
7. $1 \le n \le 300, 1 \le q \le 300, 0 \le a_i, x < 128$，对于所有 $1 \le i \le n$。分值 19 分。
8. $1 \le n \le 500, 1 \le q \le 100000, 0 \le a_i, x < 128$，对于所有 $1 \le i \le n$。分值 30 分。
9. $1 \le n \le 1000, 1 \le q \le 100000, 0 \le a_i, x < 128$，对于所有 $1 \le i \le n$。分值 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。 在第二个样例中，集合 $S$ 为空，所有子集构成的集合仅包含一个元素 $\emptyset$（空集），即没有任何更新，你需要求出给定序列 $a$ 的 $K(\emptyset)$。