أُعطيت متتالية $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)$ بأنه مجموع $\operatorname{sum}(i,j)^2$ على جميع المقاطع الممكنة من المتتالية $a$ بعد تطبيق جميع تحديثات المجموعة $S$ على المتتالية المعطاة:

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

حيث تُعرَّف $\operatorname{sum}(i,j)$ بأنها مجموع عناصر المقطع $[i,j]$:

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

مهمتك إيجاد المجموع على جميع المجموعات الجزئية البالغ عددها $2^q$ للمجموعة المعطاة $S$ من التحديثات. رسميًا، إذا كانت $P$ مجموعة جميع المجموعات الجزئية لمجموعة التحديثات $S$ ذات العناصر الـ$q$، فعليك إيجاد ما يلي:

$$\sum_{\mathit{subset}\in P}K(\mathit{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$.