import itertools
n = int(input())

a = list(map(int,input().split()))


aas = list(itertools.combinations(a,2))
m = len(aas)

x = 0
for i in range(m):
    x += ((aas[i][0] ^ aas[i][1]) % (10**7 + 9))
    x %= 10**7 + 9

print(x)

