Вам дана последовательность $a$ из $n$ целых чисел $a_1,a_2,\ldots,a_n$.

Кроме того, дано множество $S$ из $q$ обновлений. Каждое обновление задаётся тремя числами $l$, $r$ и $x$. Обновление состоит в применении операции xor с числом $x$ ко всем числам на отрезке $[l,r]$ последовательности $a$. Формально, для каждого $l \le i \le r$ выполняется следующее присваивание:

$$a_i := a_i \oplus x$$

Для множества обновлений $S$ определим $K(S)$ как сумму $sum(i,j)^2$ по всем возможным отрезкам последовательности $a$ после применения к исходной последовательности всех обновлений из множества $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$$

Ваша задача — найти сумму по всем $2^q$ подмножествам данного множества обновлений $S$. Формально, если $P$ — множество всех подмножеств множества $S$ из $q$ обновлений, нужно найти следующее:

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

Входные данные

Первая строка входных данных содержит одно целое число $n$ ($1 \le n \le 1000$) — количество элементов последовательности.

Вторая строка содержит $n$ целых чисел $a_1,a_2,\ldots,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$ пусто, множество всех подмножеств состоит из единственного элемента $\varnothing$ — пустого множества, то есть обновлений нет и нужно найти $K(\varnothing)$ для заданной последовательности $a$.