You are given a sequence $a$ of $n$ integer numbers $a_1,a_2,\ldots,a_n$.

In addition, you are given a set $S$ of $q$ updates. Each update is defined by three numbers $l$, $r$, and $x$. An update consists of the operation xor with the number $x$ applied to all the numbers in the segment $[l,r]$ of the sequence $a$. Formally, for each $l \le i \le r$ the following substitution is performed:

$$a_i := a_i \oplus x$$

For a set of updates $S$, let’s define $K(S)$ as the sum of $\operatorname{sum}(i,j)^2$ over all possible segments of the sequence $a$ after applying all updates from the set $S$ to the given sequence:

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

where $\operatorname{sum}(i,j)$ is defined as the sum of elements in the segment $[i,j]$:

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

Your task is to find the sum over all $2^q$ subsets of the given set of updates $S$. Formally, if $P$ is the set of all subsets of the set $S$ of $q$ updates, you have to find the following:

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

Input

The first line of input contains single integer $n$ ($1 \le n \le 1000$) — the number of elements in the sequence.

The second line contains $n$ space-separated integer numbers $a_1,a_2,\ldots,a_n$ ($0 \le a_i <128$ for each $1 \le i \le n$) — the given sequence.

The third line contains single integer $q$ ($1 \le q \le 10^5$) — the number of updates.

Each of the next $q$ lines contains three space-separated integer numbers $l$, $r$, and $x$ ($1 \le l \le r \le n$, $0 \le x <128$) — descriptions of the updates.

Output

Output single integer — answer to the problem. As soon as the answer may be very large, output it modulo $10^9+7$.

Subtasks

This problem consists of nine subtasks:

1. $1 \le n \le 10$, $1 \le q \le 10$, $0 \le a_i,x <128$, for all $1 \le i \le n$. Scored 4 points.
2. $1 \le n \le 100$, $1 \le q \le 10$, $0 \le a_i,x <128$, for all $1 \le i \le n$. Scored 5 points.
3. $1 \le n \le 100$, $1 \le q \le 100000$, $0 \le a_i,x <32$, for all $1 \le i \le n$. It is guaranteed that length of all update segments is equal to $1$. Scored 6 points.
4. $1 \le n \le 1000$, $1 \le q \le 500$, $0 \le a_i,x <128$, for all $1 \le i \le n$. It is guarenteed that all update segments do not intersect pairwise. Scored 9 points.
5. $1 \le n \le 30$, $1 \le q \le 20$, $0 \le a_i,x <32$, for all $1 \le i \le n$. Scored 8 points.
6. $1 \le n \le 30$, $1 \le q \le 5000$, $0 \le a_i,x <32$, for all $1 \le i \le n$. Scored 11 points.
7. $1 \le n \le 300$, $1 \le q \le 300$, $0 \le a_i,x <128$, for all $1 \le i \le n$. Scored 19 points.
8. $1 \le n \le 500$, $1 \le q \le 100000$, $0 \le a_i,x <128$, for all $1 \le i \le n$. Scored 30 points.
9. $1 \le n \le 1000$, $1 \le q \le 100000$, $0 \le a_i,x <128$, for all $1 \le i \le n$. Scored 8 points.

Examples

Input 1

2
1 3
1
1 2 2

Output 1

52

Input 2

5
1 2 3 4 5
0

Output 2

1001

Note

The xor operation is the bitwise exclusive OR.

In the first sample, there are $2^1=2$ possible sequences after applying updates — with applying the single given operation and without. In both sequences the resulting sums are equal to $26$.

In the second sample, set $S$ is empty, the set of all subsets consists of a single element $\varnothing$ — empty set, i.e. there are no updates and you have to find $K(\varnothing)$ for the given sequence $a$.