######################################################### """ ##　和＆積（MOD無し）　####################################### def mul2(a,b): return a*b def add2(a,b): return a+b def mul_inv2(a): return 1/a def add_inv2(a): return -a def identity(n): return Matrix([[int(i==j) for i in range(n)] for j in range(n)]) ########################################################### ##　和＆積（MOD有り）　####################################### MOD=10**9+7 def mul2(a,b): return a*b%MOD def add2(a,b): return (a+b)%MOD def mul_inv2(a): return pow(a,MOD-2,MOD) def add_inv2(a): return -a%MOD def identity(n): return Matrix([[int(i==j) for i in range(n)] for j in range(n)]) ########################################################### ##　論理和＆論理積　####################################### def mul2(a,b): return a&b def add2(a,b): return a^b def mul_inv2(a): return None def add_inv2(a): return a mask=(1<<32-1) def identity(n): return Matrix([[int(i==j)*mask for i in range(n)] for j in range(n)]) ########################################################### """ ######################################################### class Matrix(): def __init__(self,A): self.H=len(A) self.W=len(A[0]) self._matrix=A # for i in range(self.row): # for j in range(self.column): def __getitem__(self,item): if type(item)==tuple: i,j=item return self._matrix[i][j] else: return self._matrix[item] def __setitem__(self,item,val): i,j=item self._matrix[i][j]=val def __add__(self,B): # assert (self.row,self.column)==(other.row,other.column), "sizes of matrices are different" H,W,A=self.H,self.W,self._matrix AB=[[0]*W for _ in range(H)] for h in range(H): for w in range(W): AB[h][w]=add2(A[h][w],B._matrix[h][w]) return Matrix(AB) def __mul__(self,other): H,W,A=self.H,self.W,self._matrix if type(other)==int: n=other AB=[[(mul2(n,A[i][j])) for j in range(W)] for i in range(H)] return Matrix(AB) elif type(other)==Vector: vec=other res=[0]*W for i in range(H): for j in range(W): res[i]=add2(res[i],mul2(A[i][j],vec[j])) return Vector(res) else: # assert self.column!=other.row, "sizes of matrices are different" AB=[[0]*other.W for _ in range(H)] for i in range(H): for j in range(other.W): temp=0 for k in range(W): temp=add2(temp,mul2(A[i][k],other._matrix[k][j])) AB[i][j]=temp return Matrix(AB) def __truediv__(self,c): H,W,A=self.H,self.W,self._matrix res=A.copy() for h in range(H): for w in range(W): res[h][w]=mul2(res[h][w],mul_inv2(c)) return Matrix(res) def __floordiv__(self,c): H,W,A=self.H,self.W,self._matrix res=A.copy() for h in range(H): for w in range(W): res[h][w]=res[h][w]//c return Matrix(res) def __mod__(self,c): H,W,A=self.H,self.W,self._matrix res=A.copy() for h in range(H): for w in range(W): res[h][w]=res[h][w]%c return Matrix(res) def map(self,func): # act func to all elements H,W,A=self.H,self.W,self._matrix res=A.copy() for h in range(H): for w in range(W): res[h][w]=func(res[h][w]) return Matrix(res) def __pow__(self,m): # assert self.column==self.row, "the size of row must be the same as that of column" H,W,A=self.H,self.W,self._matrix res=identity(H) while m: if m%2==1: res=res*self self=self*self m>>=1 return res def det(self): H,W,A=self.H,self.W,self._matrix n=H res=1 for i in range(n): if A[i][i]==0: res=add_inv2(res) for k in range(i+1,n): if A[k][i]!=0: A[i],A[k]=A[k],A[i] break else: return 0 c=mul_inv2(A[i][i]) for j in range(i+1,n): l=mul2(c,A[j][i]) for k in range(i+1,n): A[j][k]=add2(A[j][k],add_inv2(l*A[i][k])) for i in range(n): res=mul2(res,A[i][i]) return res def __eq__(self,other): if type(other)==Matrix: return self._matrix==other._matrix return False def __ne__(self,other): if type(other)==Matrix: return self._matrix!=other._matrix return True def __len__(self): return self.H def __str__(self): res=[] for i in range(self.H): for j in range(self.W): res.append(str(self._matrix[i][j])) res.append(" ") res.append("\n") return "".join(res) def __hash__(self): res=[] for h in range(self.H): for w in range(self.W): res.append(self._matrix[h][w]) return tuple(res) def count(self,x): cnt=0 for h in range(self.H): for w in range(self.W): cnt+=(self._matrix[h][w]==x) return cnt def rank(self): """ = dimension""" H,W,A=self.H,self.W,self._matrix A=[self._matrix[i][:] for i in range(H)] rank=0 p,q=[],[] for w in range(W): for h in range(rank,H): if A[h][w]!=0: break else: q.append(w) continue if w==W: return -1,[],[] p.append(w) A[rank],A[h]=A[h],A[rank] inv=mul_inv2(A[rank][w]) for ww in range(W): A[rank][ww]=mul2(A[rank][ww],inv) for h in range(H): if h==rank: continue c=add_inv2(A[h][w]) for ww in range(W): A[h][ww]=add2(A[h][ww],mul2(c,A[rank][ww])) rank+=1 return rank class Vector(): def __init__(self,vec): self.n=len(vec) self._vector=vec def __getitem__(self,item): return self._vector[item] def __setitem__(self,item,val): self._vector[item]=val def __neg__(self): n,vec=self.n,self._vector res=[] for x in vec: res.append(add_inv2(x)) return Vector(res) def __add__(self,vec2): n,vec=self.n,self._vector res=vec.copy() for i in range(n): res[i]=add2(res[i],vec2[i]) return Vector(res) def __sub__(self,vec2): n,vec=self.n,self._vector res=vec.copy() for i in range(n): res[i]=add2(res[i],add_inv2(vec2[i])) return Vector(res) def __mul__(self,vec2): n,vec=self.n,self._vector if type(vec2)!=int: res=vec.copy() for i in range(n): res[i]=mul2(res[i],vec2[i]) return Vector(res) else: res=[mul2(vec2,vec[i]) for i in range(n)] return Vector(res) def __truediv__(self,c): n,vec=self.n,self._vector res=vec.copy() for i in range(n): res[i]=mul2(res[i],mul_inv2(c)) return Vector(res) def __floordiv__(self,c): n,vec=self.n,self._vector res=vec.copy() for i in range(n): res[i]=res[i]//c return Vector(res) def __mod__(self,c): n,vec=self.n,self._vector res=vec.copy() for i in range(n): res[i]=res[i]%c return Vector(res) def map(self,func): # act func to all elements n,vec=self.n,self._vector res=vec.copy() for i in range(n): res[i]=func(res[i]) return Vector(res) def __eq__(self,other): if type(other)==Vector: return self._vector==other._vector return False def __ne__(self,other): if type(other)==Vector: return self._vector!=other._vector return True def __len__(self): return self.n def __str__(self): res=[] for i in range(self.n): res.append(str(self._vector[i])) res.append(" ") return "".join(res) def __hash__(self): return tuple(self._vector) def count(self,x): cnt=0 for a in self._vector: cnt+=(a==x) return cnt def linear_equations(mat,vec): """ return (dim, [x,y,z], [[a0,b0,c0],[a1,b1,c1],...]) which means, solution = (x,y,z)+t0*(a0,b0,c0)+t1*(a1,b1,c1)+... Cation: float """ H,W=len(mat),len(mat[0]) # assert H == len(vec) aug=[mat[i]+[vec[i]] for i in range(H)] rank=0 p,q=[],[] for w in range(W+1): for h in range(rank,H): if aug[h][w]!=0: break else: q.append(w) continue if w==W: return -1,[],[] p.append(w) aug[rank],aug[h]=aug[h],aug[rank] inv=mul_inv2(aug[rank][w]) for ww in range(W+1): aug[rank][ww]=mul2(aug[rank][ww],inv) for h in range(H): if h==rank: continue c=add_inv2(aug[h][w]) for ww in range(W+1): aug[h][ww]=add2(aug[h][ww],mul2(c,aug[rank][ww])) rank+=1 dim=W-rank sol=[0]*W for h in range(rank): sol[p[h]]=aug[h][-1] vecs=[[0]*W for _ in range(dim)] for h in range(dim): vecs[h][q[h]]=1 for h in range(dim): for w in range(rank): vecs[h][p[w]]=add_inv2(aug[w][q[h]]) return dim,sol,vecs ########################################################### def example(): global input example=iter( """ 3 3 1 0 0 1 0 1 0 0 1 """ .strip().split("\n")) input=lambda:next(example) ##　和＆積（MOD有り）　####################################### MOD=2 def mul2(a,b): return a*b%MOD def add2(a,b): return (a+b)%MOD def mul_inv2(a): return pow(a,MOD-2,MOD) def add_inv2(a): return -a%MOD def identity(n): return Matrix([[int(i==j) for i in range(n)] for j in range(n)]) def bit_rep(bit,N): return format(bit, "0" + str(N) + "b") ########################################################### import sys input=sys.stdin.readline # example() N=int(input()) A=list(map(int, input().split())) mat=[] for a in A: vec=[] for b in bit_rep(a,62): vec.append(int(b)) mat.append(vec) mat=Matrix(mat) rank=mat.rank() print(pow(2,rank))