נתונה לכם סדרה $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$.