เรากล่าวว่าเซต $S$ ของจำนวนเต็มไม่ติดลบเป็นเซตแบบ ไม่รวมค่า XOR (XOR-excluding) ถ้าผลลัพธ์ XOR ของสมาชิกทั้งหมดใน $S$ ไม่ได้อยู่ในเซต $S$ นั้นเอง
กำหนดเซต $A$ ที่เริ่มต้นเป็นเซตว่าง เราจะเพิ่มสมาชิกจำนวนเต็มบวกที่แตกต่างกัน $n$ ตัว คือ $a_i$ เข้าไปทีละตัว หลังจากการเพิ่มแต่ละครั้ง จงหาจำนวนสับเซตแบบไม่รวมค่า XOR ของ $A$
เนื่องจากคำตอบอาจมีค่าใหญ่มาก จงแสดงผลลัพธ์มอดุโล $10^9 + 7$
ข้อมูลนำเข้า
บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $n$ เพียงตัวเดียว — จำนวนสมาชิกที่จะเพิ่ม
อีก $n$ บรรทัดถัดมา แต่ละบรรทัดประกอบด้วยจำนวนเต็ม $a_i$ เพียงตัวเดียว — สมาชิกตัวที่ $i$ ที่จะเพิ่มเข้าไปในเซต
ข้อมูลส่งออก
พิมพ์ $n$ บรรทัด ในบรรทัดที่ $i$ ให้พิมพ์จำนวนสับเซตแบบไม่รวมค่า XOR ของ $A$ หลังจากเพิ่มสมาชิก $i$ ตัวแรก มอดุโล $10^9 + 7$
ข้อจำกัด
- $1 \le n \le 2 \cdot 10^5$,
- $1 \le a_i \le 2^{60} - 1$,
- $a_i$ ทั้งหมดมีค่าแตกต่างกัน
ตัวอย่าง 1
5
1
2
3
4
5
1
2
5
11
22
หมายเหตุ
หลังจากเพิ่ม $1$ สับเซตแบบไม่รวมค่า XOR เพียงตัวเดียวคือ $\{\}$ (เซตว่างมีค่า XOR เท่ากับ $0$)
หลังจากเพิ่ม $2$ สับเซตแบบไม่รวมค่า XOR คือ $\{\}$ และ $\{1, 2\}$ (ซึ่งมีค่า XOR เท่ากับ $3$)
หลังจากเพิ่ม $3$ สับเซตแบบไม่รวมค่า XOR คือ $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{2, 3\}$ และ $\{1, 2, 3\}$
หลังจากเพิ่ม $4$ สับเซตแบบไม่รวมค่า XOR คือ $\{\}$, $\{1, 2\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 3\}$, $\{2, 4\}$, $\{3, 4\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{1, 3, 4\}$ และ $\{2, 3, 4\}$ สังเกตว่า $\{1, 2, 3, 4\}$ มีค่า XOR เท่ากับ $3$ ดังนั้นจึงไม่เป็นเซตแบบไม่รวมค่า XOR