음이 아닌 정수로 이루어진 집합 $S$의 모든 원소의 배타적 논리합(XOR)이 집합 $S$ 자체에 속하지 않을 때, 집합 $S$를 XOR 배제(XOR-excluding) 집합이라고 부릅니다.
처음에 비어 있는 집합 $A$가 주어지고, 여기에 $n$개의 서로 다른 양의 원소 $a_i$를 하나씩 차례대로 추가합니다. 원소를 하나 추가할 때마다, $A$의 부분집합 중 XOR 배제 집합의 개수를 구하세요.
정답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력합니다.
입력
입력의 첫 번째 줄에는 추가할 원소의 개수를 나타내는 정수 $n$이 주어집니다.
다음 $n$개의 줄에는 각각 집합에 $i$번째로 추가할 원소를 나타내는 정수 $a_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 배제 집합이 아님에 유의하세요.