نقول إن مجموعة $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.