נאמר שקבוצה $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.