Вам дано послідовність $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$.