Теріс емес бүтін сандардан тұратын $S$ жиынының барлық элементтерінің XOR мәні $S$ жиынының өзінде жатпаса, онда $S$ жиынын XOR-шығарушы (XOR-excluding) деп атаймыз.
Бастапқыда бос $A$ жиыны берілген, біз оған бір-бірлеп $n$ әртүрлі оң $a_i$ элементтерін қосамыз. Әр қосудан кейін $A$ жиынының XOR-шығарушы ішкі жиындарының санын табыңыз.
Жауап өте үлкен болуы мүмкін болғандықтан, оны $10^9 + 7$ модулі бойынша шығарыңыз.
Кіріс деректер
Кіріс деректердің бірінші жолында бір бүтін сан $n$ — қосылатын элементтер саны берілген.
Келесі $n$ жолдың әрқайсысында бір бүтін сан $a_i$ — жиынға қосылатын $i$-ші элемент берілген.
Шығыс деректер
$n$ жол шығарыңыз. $i$-ші жолда алғашқы $i$ элементті қосқаннан кейінгі $A$ жиынының XOR-шығарушы ішкі жиындарының санын $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-шығарушы емес.