Chandrima likes the XOR operation very much and keeps finding and solving related problems. One day she comes across a problem and gets stuck on it, which makes her sad. You being her friend decide to help her out by writing a code for the same. 

Consider a list of all natural numbers. Now you remove all numbers whose binary representation has at least two consecutive ${1}$ bits, from the list, hence generating a new list having elements $1,2,4,5,8,\ldots$ and so on. Now you are given $N$ numbers from this newly generated list. You have to find the XOR of these numbers.

Input Format 

The first line has an integer $N$, denoting the number of integers in list ${A}$. 

The next line contains $N$ space-separated integers. $A_i$ represents the $A_i^{\text{th}}$ number of the generated list. Since the answer can be very large, print the answer modulo $(10^9+7)$.

Output Format 

Just print one line containing the final answer.  

Constraints 

$1\leq N\leq5\cdot10^5$ 

$1\leq A_i\leq10^{18}$

Sample Input 1  

3
1 2 3

Sample Output 1  

7

Sample Input 2  

3
1 3 4

Sample Output 2  

0

Explanation  

Sample 1: 

The values to be considered are $1,2,4$, and the answer is $1\oplus2\oplus4=7$.

Sample 2: 

The values to be considered are $1,4,5$, and the answer is $1\oplus4\oplus5=0$.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Number theory


Solutions:
import functools, operator as op, sys
MAX = 10 ** 18
MOD = 1000000007
FIBONACCI = [1, 2]
while FIBONACCI[-1] <= MAX:
	FIBONACCI.append(FIBONACCI[-1] + FIBONACCI[-2])
POWERS = [pow(2, i) for i in range(len(FIBONACCI))]

def zeckendorf_number(n):
	result = 0
	for i in reversed(range(len(FIBONACCI))):
		if n >= FIBONACCI[i]:
			result += POWERS[i]
			n -= FIBONACCI[i]
	return result
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
print(functools.reduce(op.xor, (zeckendorf_number(a) for a in A)) % MOD)


import functools, operator as op, sys
MAX = 10 ** 18
MOD = 1000000007
FIBONACCI = [1, 2]
while FIBONACCI[-1] <= MAX:
	FIBONACCI.append(FIBONACCI[-1] + FIBONACCI[-2])
POWERS = [pow(2, i) for i in range(len(FIBONACCI))]

def zeckendorf_number(n):
	result = 0
	for i in reversed(range(len(FIBONACCI))):
		if n >= FIBONACCI[i]:
			result += POWERS[i]
			n -= FIBONACCI[i]
	return result
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
print(functools.reduce(op.xor, (zeckendorf_number(a) for a in A)) % MOD)


import functools, operator as op, sys
MAX = 10 ** 18
MOD = 1000000007
FIBONACCI = [1, 2]
while FIBONACCI[-1] <= MAX:
	FIBONACCI.append(FIBONACCI[-1] + FIBONACCI[-2])
POWERS = [pow(2, i) for i in range(len(FIBONACCI))]

def zeckendorf_number(n):
	result = 0
	for i in reversed(range(len(FIBONACCI))):
		if n >= FIBONACCI[i]:
			result += POWERS[i]
			n -= FIBONACCI[i]
	return result
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
print(functools.reduce(op.xor, (zeckendorf_number(a) for a in A)) % MOD)


M = 1000000007
MAX = 1e+19
fibonaccis = [1, 2]
i = 0
j = 1
while fibonaccis[j] <= MAX:
	fibonaccis.append(fibonaccis[i] + fibonaccis[j])
	i += 1
	j += 1
powers = [2 ** i for i in range(len(fibonaccis))]

def f(n):
	res = 0
	for i in range(len(fibonaccis) - 1, -1, -1):
		if n >= fibonaccis[i]:
			res += powers[i]
			n -= fibonaccis[i]
	return res
n = int(input())
vals = list(map(int, input().split()))
f_list = [f(i) for i in vals]
xor_res = 0
for r in f_list:
	xor_res ^= r
print(xor_res % M)


import sys
MAX = 10 ** 18
MOD = 10 ** 9 + 7
FIBO = [1, 2]
while FIBO[-1] <= MAX:
	FIBO.append(FIBO[-1] + FIBO[-2])
POWER = [pow(2, i) for i in range(len(FIBO))]

def fibonacciBase(a):
	base = 0
	for i in reversed(range(len(FIBO))):
		if a >= FIBO[i]:
			base += POWER[i]
			a -= FIBO[i]
	return base

def computeXOR(list):
	newList = []
	for i in list:
		newList.append(fibonacciBase(i))
	xor = newList[0]
	for i in range(1, len(newList)):
		xor = xor ^ newList[i]
	return xor % MOD
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
result = computeXOR(A)
print(result)


M = 1000000007
MAX = 1e+19
fibonaccis = [1, 2]
i = 0
j = 1
while fibonaccis[j] <= MAX:
	fibonaccis.append(fibonaccis[i] + fibonaccis[j])
	i += 1
	j += 1
powers = [2 ** i for i in range(len(fibonaccis))]

def f(n):
	res = 0
	for i in range(len(fibonaccis) - 1, -1, -1):
		if n >= fibonaccis[i]:
			res += powers[i]
			n -= fibonaccis[i]
	return res
n = int(input())
vals = list(map(int, input().split()))
f_list = [f(i) for i in vals]
xor_res = 0
for r in f_list:
	xor_res ^= r
print(xor_res % M)


P = 10 ** 9 + 7
Amax = 10 ** 18
F = [1, 2]
while F[-1] < Amax:
	F.append(F[-1] + F[-2])

def get_kth(k):
	n = len(F) - 1
	res = 0
	while n > 0:
		res <<= 1
		if k >= F[n - 1]:
			k -= F[n - 1]
			res |= 1
		n -= 1
	return res

def main():
	N = int(input())
	A = list(map(int, input().split()))
	X = 0
	for a in A:
		X ^= get_kth(a)
	print(X % P)
main()


M = 1000000007
MAX = 1e+19
fibonaccis = [1, 2]
i = 0
j = 1
while fibonaccis[j] <= MAX:
	fibonaccis.append(fibonaccis[i] + fibonaccis[j])
	i += 1
	j += 1
powers = [2 ** i for i in range(len(fibonaccis))]

def f(n):
	res = 0
	for i in range(len(fibonaccis) - 1, -1, -1):
		if n >= fibonaccis[i]:
			res += powers[i]
			n -= fibonaccis[i]
	return res
n = int(input())
vals = list(map(int, input().split()))
f_list = [f(i) for i in vals]
xor_res = 0
for r in f_list:
	xor_res ^= r
print(xor_res % M)


import functools, operator as op, sys
MAX = 10 ** 18
MOD = 1000000007
FIBONACCI = [1, 2]
while FIBONACCI[-1] <= MAX:
	FIBONACCI.append(FIBONACCI[-1] + FIBONACCI[-2])
POWERS = [pow(2, i) for i in range(len(FIBONACCI))]

def zeckendorf_number(n):
	result = 0
	for i in reversed(range(len(FIBONACCI))):
		if n >= FIBONACCI[i]:
			result += POWERS[i]
			n -= FIBONACCI[i]
	return result
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
print(functools.reduce(op.xor, (zeckendorf_number(a) for a in A)) % MOD)


fibList = [1, 1]
while fibList[-1] < 10 ** 18:
	fibList.append(fibList[-1] + fibList[-2])

def presentationAsFibonacci(n):
	from bisect import bisect_right
	num = 0
	while True:
		pos = bisect_right(fibList, n) - 1
		if n <= 0:
			break
		num += 1 << pos - 1
		n -= fibList[pos]
	return num
input()
res = 0
for i in list(map(int, input().split())):
	res ^= presentationAsFibonacci(i)
print(res % (10 ** 9 + 7))


import functools, operator as op, sys
MAX = 10 ** 18
MOD = 1000000007
FIBONACCI = [1, 2]
while FIBONACCI[-1] <= MAX:
	FIBONACCI.append(FIBONACCI[-1] + FIBONACCI[-2])
POWERS = [pow(2, i) for i in range(len(FIBONACCI))]

def zeckendorf_number(n):
	result = 0
	for i in reversed(range(len(FIBONACCI))):
		if n >= FIBONACCI[i]:
			result += POWERS[i]
			n -= FIBONACCI[i]
	return result
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
print(functools.reduce(op.xor, (zeckendorf_number(a) for a in A)) % MOD)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


import functools, operator as op, sys
MAX = 10 ** 18
MOD = 1000000007
FIBONACCI = [1, 2]
while FIBONACCI[-1] <= MAX:
	FIBONACCI.append(FIBONACCI[-1] + FIBONACCI[-2])
POWERS = [pow(2, i) for i in range(len(FIBONACCI))]

def zeckendorf_number(n):
	result = 0
	for i in reversed(range(len(FIBONACCI))):
		if n >= FIBONACCI[i]:
			result += POWERS[i]
			n -= FIBONACCI[i]
	return result
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
print(functools.reduce(op.xor, (zeckendorf_number(a) for a in A)) % MOD)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


import functools, operator as op, sys
MAX = 10 ** 18
MOD = 1000000007
FIBONACCI = [1, 2]
while FIBONACCI[-1] <= MAX:
	FIBONACCI.append(FIBONACCI[-1] + FIBONACCI[-2])
POWERS = [pow(2, i) for i in range(len(FIBONACCI))]

def zeckendorf_number(n):
	result = 0
	for i in reversed(range(len(FIBONACCI))):
		if n >= FIBONACCI[i]:
			result += POWERS[i]
			n -= FIBONACCI[i]
	return result
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
print(functools.reduce(op.xor, (zeckendorf_number(a) for a in A)) % MOD)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


import functools, operator as op, sys
MAX = 10 ** 18
MOD = 1000000007
FIBONACCI = [1, 2]
while FIBONACCI[-1] <= MAX:
	FIBONACCI.append(FIBONACCI[-1] + FIBONACCI[-2])
POWERS = [pow(2, i) for i in range(len(FIBONACCI))]

def zeckendorf_number(n):
	result = 0
	for i in reversed(range(len(FIBONACCI))):
		if n >= FIBONACCI[i]:
			result += POWERS[i]
			n -= FIBONACCI[i]
	return result
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
print(functools.reduce(op.xor, (zeckendorf_number(a) for a in A)) % MOD)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


import functools, operator as op, sys
MAX = 10 ** 18
MOD = 1000000007
FIBONACCI = [1, 2]
while FIBONACCI[-1] <= MAX:
	FIBONACCI.append(FIBONACCI[-1] + FIBONACCI[-2])
POWERS = [pow(2, i) for i in range(len(FIBONACCI))]

def zeckendorf_number(n):
	result = 0
	for i in reversed(range(len(FIBONACCI))):
		if n >= FIBONACCI[i]:
			result += POWERS[i]
			n -= FIBONACCI[i]
	return result
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
print(functools.reduce(op.xor, (zeckendorf_number(a) for a in A)) % MOD)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


import os
import sys

def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


import os
import sys

def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < max(nums):
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


import os
import sys

def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


import os
import sys

def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)


import os
import sys

def zeck(n):
	res = 0
	for i in range(f - 1, -1, -1):
		if n >= fib[i]:
			n -= fib[i]
			res += p2[i]
	return res
n = int(input())
nums = list(map(int, input().strip().split()))
fib = [1, 2, 3]
while fib[-1] < 10 ** 18:
	fib.append(fib[-1] + fib[-2])
f = len(fib)
p2 = []
for j in range(f):
	p2.append(2 ** j)
modulus = 10 ** 9 + 7
sol = 0
for j in range(n):
	sol = sol ^ zeck(nums[j])
print(sol % modulus)