กำหนดลำดับ $a$ ที่ประกอบด้วยจำนวนเต็ม $n$ จำนวน $a_1,a_2,\ldots,a_n$

นอกจากนี้ กำหนดเซต $S$ ของการปรับปรุง $q$ รายการ การปรับปรุงแต่ละรายการระบุด้วยจำนวนสามจำนวน $l,r,x$ โดยนำจำนวน $x$ ไปดำเนินการ xor กับจำนวนทุกจำนวนในช่วง $[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_{subset\in P}K(subset)$$

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้ามีจำนวนเต็ม $n$ ($1\le n\le1000$) ซึ่งเป็นจำนวนสมาชิกของลำดับ

บรรทัดที่สองมีจำนวนเต็ม $n$ จำนวน $a_1,a_2,\ldots,a_n$ คั่นด้วยช่องว่าง ($0\le a_i<128$ สำหรับทุก $1\le i\le n$) ซึ่งเป็นลำดับที่กำหนด

บรรทัดที่สามมีจำนวนเต็ม $q$ ($1\le q\le10^5$) ซึ่งเป็นจำนวนการปรับปรุง

แต่ละบรรทัดใน $q$ บรรทัดถัดไปมีจำนวนเต็มสามจำนวน $l,r,x$ คั่นด้วยช่องว่าง ($1\le l\le r\le n$, $0\le x<128$) ซึ่งอธิบายการปรับปรุง

ข้อมูลส่งออก

พิมพ์จำนวนเต็มหนึ่งจำนวน คือคำตอบของโจทย์ เนื่องจากคำตอบอาจมีค่ามาก ให้พิมพ์เศษจากการหารคำตอบด้วย $10^9+7$

งานย่อย

โจทย์นี้มีงานย่อยเก้างาน:

1. $1\le n\le10$, $1\le q\le10$, $0\le a_i,x<128$ สำหรับทุก $1\le i\le n$ ได้ 4 คะแนน
2. $1\le n\le100$, $1\le q\le10$, $0\le a_i,x<128$ สำหรับทุก $1\le i\le n$ ได้ 5 คะแนน
3. $1\le n\le100$, $1\le q\le100000$, $0\le a_i,x<32$ สำหรับทุก $1\le i\le n$ รับประกันว่าช่วงของการปรับปรุงทุกรายการมีความยาวเท่ากับ $1$ ได้ 6 คะแนน
4. $1\le n\le1000$, $1\le q\le500$, $0\le a_i,x<128$ สำหรับทุก $1\le i\le n$ รับประกันว่าช่วงของการปรับปรุงทุกคู่ไม่ตัดกัน ได้ 9 คะแนน
5. $1\le n\le30$, $1\le q\le20$, $0\le a_i,x<32$ สำหรับทุก $1\le i\le n$ ได้ 8 คะแนน
6. $1\le n\le30$, $1\le q\le5000$, $0\le a_i,x<32$ สำหรับทุก $1\le i\le n$ ได้ 11 คะแนน
7. $1\le n\le300$, $1\le q\le300$, $0\le a_i,x<128$ สำหรับทุก $1\le i\le n$ ได้ 19 คะแนน
8. $1\le n\le500$, $1\le q\le100000$, $0\le a_i,x<128$ สำหรับทุก $1\le i\le n$ ได้ 30 คะแนน
9. $1\le n\le1000$, $1\le q\le100000$, $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 คือการดำเนินการ exclusive OR ระดับบิต

ในตัวอย่างแรก มีลำดับที่เป็นไปได้หลังจากใช้การปรับปรุง $2^1=2$ ลำดับ ได้แก่ กรณีที่ใช้การปรับปรุงเพียงรายการเดียวที่กำหนด และกรณีที่ไม่ใช้ ในทั้งสองลำดับ ผลรวมที่ได้เท่ากับ $26$

ในตัวอย่างที่สอง เซต $S$ ว่างเปล่า เซตของสับเซตทั้งหมดมีสมาชิกเพียงตัวเดียว คือ $\varnothing$ ซึ่งเป็นเซตว่าง กล่าวคือไม่มีการปรับปรุง และคุณต้องหา $K(\varnothing)$ สำหรับลำดับ $a$ ที่กำหนด