You are given an array with $n$ $64$-bit integers: $d[0],d[1],\ldots,d[n-1].$.

BIT(x, i) = (x >> i) & 1, where $B(x,i)$ is the $i^{th}$ lower bit of $x$ in binary form.  If we regard every bit as a vertex of a graph G, there is an undirected edge between vertices $i$ and $j$ if there is a value $k$ such that BIT(d[k], i) == 1 && BIT(d[k], j) == 1.

For every subset of the input array, how many  connected-components are there in that graph?

A connected component in a graph is a set of nodes which are accessible to each other via a path of edges. There may be multiple connected components in a graph.  

Example 

$d=\{1,2,3,5\}$  

In the real challenge, there will be $64$ nodes associated with each integer in $d$ represented as a $64$ bit binary value.  For clarity, only $4$ bits will be shown in the example but all $64$ will be considered in the calculations.      

    Decimal  Binary Edges   Node ends
    d[0] = 1   0001   0
    d[1] = 2   0010   0
    d[2] = 3   0011   1       0 and 1
    d[3] = 5   0101   1       0 and 2

Consider all subsets:

                 Edges
    Subset   Count  Nodes  Connected components
    {1}         0           64
    {2}         0           64
    {3}         1   0-1     63
    {5}         1   0-2     63
    {1,2}       0           64
    {1,3}       1   0-1     63
    {1,5}       1   0-2     63
    {2,3}       1   0-1     63
    {2,5}       1   0-2     63
    {3,5}       2   0-1-2   62
    {1,2,3}     1   0-1     63
    {1,2,5}     1   0-2     63
    {1,3,5}     2   0-1-2   62
    {2,3,5}     2   0-1-2   62
    {1,2,3,5}   2   0-1-2   62
    Sum                    944

The values $3$ and $5$ have $2$ bits set, so they have $1$ edge each.  If a subset contains only a $3$ or $5$, there will be one connected component with $2$ nodes, and $62$ components with $1$ node for a total of $63$.  

If both $3$ and $5$ are in a subset, $1$ component with nodes $0,1$ and $2$ is formed since node $0$ is one end of each edge described.  The other $61$ nodes are solitary, so there are $62$ connected components total.  

All other values have only $1$ bit set, so they have no edges.  They have $64$ components with $1$ node each.

Function Description  

Complete the findConnectedComponents function in the editor below.  

findConnectedComponents has the following parameters:  

int d[n]: an array of integers  

Returns  

int: the sum of the number of connected components for all subsets of $d$

Input Format

The first row contains the integer $n$, the size of $d[]$. 

The next row has $n$ space-separated integers, $d[i]$.  

Constraints

$1\leq n\leq20$ 

$0\le d[i]\le2^{63}-1$
Sample Input 1
3
2 5 9

Sample Output 1
504

Explanation 1 
There are  $8$ subset of $\{2,5,9\}$ .

{}
=> We don't have any number in this subset => no edge in the graph => Every node is a component by itself => Number of connected-components = 64.

{2}
=> The Binary Representation of 2 is . $00000010$There is a bit at only one position. => So there is no edge in the graph, every node is a connected-component by itself => Number of connected-components = 64.

{5}
=> The Binary Representation of 5 is . $00000101$There is a bit at the 0th and 2nd position. => So there is an edge: (0, 2) in the graph => There is one component with a pair of nodes (0,2) in the graph. Apart from that, all remaining 62 vertices are indepenent components of one node each (1,3,4,5,6...63) => Number of connected-components = 63.

{9}
=> The Binary Representation of 9 is$00001001$ . => There is a 1-bit at the 0th and 3rd position in this binary representation. => edge: (0, 3) in the graph => Number of components = 63

{2, 5}
=> This will contain the edge (0, 2) in the graph which will form one component
=> Other nodes are all independent components
=> Number of connected-component = 63

{2, 9}
=> This has edge (0,3) in the graph
=> Similar to examples above, this has 63 connected components

{5, 9}
=> This has edges (0, 2) and (0, 3) in the graph
=> Similar to examples above, this has 62 connected components

{2, 5, 9}
=> This has edges(0, 2) (0, 3) in the graph. All three vertices (0,2,3) make one component => Other 61 vertices are all independent components
=> Number of connected-components = 62
$S=64+64+63+63+63+63+63+62+62=504$

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Graph algorithms


Solutions:
from functools import reduce
from operator import or_

def get_integers():
	from sys import stdin
	return (int(stdin.readline().strip()), sorted(map(int, stdin.readline().strip().split())))

def dec(s):
	return '{:b}'.format(s).count('1') - 1 if s else 0

def compute(head, *tail):
	hc = dec(head)
	if tail:
		(last, d) = compute(*tail)
		new = []
		d_ = d
		for (k, v) in last:
			if all((t & head == 0 for t in k)):
				x = v + hc
				d_ += x
				new.append((k + (head,), x))
			else:
				A = tuple((t for t in k if t & head == 0))
				b = reduce(or_, (t for t in k if t & head != 0), head)
				x = dec(sum(A) + b) - len(A)
				d_ += x
				new.append((A + (b,), x))
		new_ = new + last
		return (new_, d_)
	else:
		return ([((), 0), ((head,), hc)], hc)
(n, I) = get_integers()
print(64 * 2 ** n - compute(*I)[1])


def subset(d, n):
	r = []
	for (i, x) in enumerate(d):
		if n & 1 << i != 0:
			r += [x]
	return r

def nzeroes(x):
	return sum((1 if x & 1 << i == 0 else 0 for i in range(64)))

def components(d, colors, color):
	r = []
	used = [False] * len(d)
	for i in range(len(d)):
		if not used[i]:
			x = d[i]
			used[i] = True
			for j in range(i + 1, len(d)):
				if not used[j] and x ^ d[j] != x | d[j]:
					x = x | d[j]
					used[j] = True
			r += [x]
	s = 0
	for x in r:
		s = s | x
	return nzeroes(s) + len(r)

def bfsBitColor(d):
	n = len(d)
	color = [None] * n
	c = 0
	for i in range(n):
		if color[i] is None:
			q = [i]
			while len(q) > 0:
				v = q[0]
				q = q[1:]
				color[v] = c
				for u in range(n):
					if color[u] is None and d[u] & d[v] != 0:
						q += [u]
			c += 1
	return color

def lost(k, n):
	return (1 << n - k) * (k * (1 << k - 1) - (1 << k) + 1)
nn = int(input())
d = [int(x) for x in input().split()]
d = [x for x in d if x != 0]
n = len(d)
if n > 0:
	color = bfsBitColor(d)
	colors = max(color) + 1
	colorsCount = [0] * colors
	for i in range(n):
		colorsCount[color[i]] += 1
	ones = [0] * 64
	for i in range(64):
		ones[i] = sum((1 if x & 1 << i != 0 else 0 for x in d))
	r = 0
	usedColorsTotal = n * (1 << n - 1) - sum((lost(k, n) for k in colorsCount))
	r = usedColorsTotal
	onesTotal = sum(((1 << n) - (1 << n - k) for k in ones))
	r += 64 * (1 << n) - onesTotal
	r = r << nn - n
	print(r)
else:
	print(64 << nn)


import collections
import functools
import math
import itertools
l = int(input())
vs = map(int, input().split())
singlebits = {}
for i in map(lambda x: 1 << x, range(0, 64)):
	singlebits[i] = True

def multibit(v):
	if v == 0 or v in singlebits:
		return 1
	return v
vs = list(map(multibit, vs))
queue = list(itertools.chain.from_iterable(map(lambda i: itertools.combinations(vs, i), range(1, len(vs) + 1))))
baseGroups = list(map(lambda x: 1 << x, range(0, 64)))
cache = {}
cache[()] = []
sum = 64
for d in queue:
	if d in cache:
		newgroups = cache[d]
	else:
		groups = cache[d[0:-1]]
		i = d[-1]
		m = i
		newgroups = []
		for g in groups:
			if g & i:
				m |= g
			else:
				newgroups.append(g)
		newgroups.append(m)
		cache[d] = newgroups
	m = functools.reduce(lambda t, x: t | x, newgroups, 0)
	disjoint = 64 - bin(m).count('1') + len(newgroups)
	sum += disjoint
print(sum)


from functools import reduce
from operator import or_
input_fn = input

def get_int():
	return int(input_fn())

def get_int_list():
	return [int(i) for i in input_fn().split()]

def positions(k):
	for i in range(64):
		if k & 1 == 1:
			yield i
		k //= 2

def count_one(v):
	s = 0
	while v != 0:
		v &= v - 1
		s += 1
	return s
from itertools import compress

def solve(nums):
	(n_empty, real_vals) = (0, [])
	for v in nums:
		if count_one(v) > 1:
			real_vals.append(v)
		else:
			n_empty += 1
	nums = real_vals

	def _solve(k, vals):
		if k == len(nums):
			if len(vals) > 0:
				v = reduce(or_, vals)
				ones = count_one(v)
				return len(vals) + 64 - ones
			else:
				return 64
		else:
			s1 = _solve(k + 1, vals)
			v = nums[k]
			new_vals = []
			for (i, v2) in enumerate(vals):
				connect = v & v2
				if connect:
					v |= v2
				else:
					new_vals.append(v2)
			new_vals.append(v)
			s2 = _solve(k + 1, new_vals)
			return s1 + s2
	print(_solve(0, []) * 2 ** n_empty)

def main():
	get_int()
	nums = get_int_list()
	solve(nums)
main()


import sys
from array import array

def intlist(n):
	return [i for i in range(64) if n >> i & 1]

def combine(entry, newlist):
	(compcount, whichcomp) = entry
	s = set((whichcomp[i] for i in newlist))
	if len(s) <= 1:
		return entry
	newcomp = s.pop()
	return (compcount - len(s), ''.join((newcomp if elt in s else elt for elt in whichcomp)))

def main():
	n = int(input())
	d = [int(fld) for fld in input().split()]
	assert n <= 20 and len(d) == n
	comptbl = [(64, ''.join((chr(i) for i in range(64))))]
	for delt in d:
		ilist = intlist(delt)
		comptbl += [combine(entry, ilist) for entry in comptbl]
	print(sum((count for (count, _) in comptbl)))
try:
	main()
except MemoryError:
	print(-1)


import itertools
import math

def comp(s, z, i):
	if 0 in z:
		z.remove(0)
	if i == len(s):
		tot = 0
		for x in z:
			tot |= x
		return 64 - '{0:b}'.format(tot).count('1') + len(z)
	repl = []
	val = s[i]
	for x in z:
		if s[i] & x != 0:
			repl.append(x)
			val |= x
	return comp(s, z[:], i + 1) + comp(s, [x for x in z if x not in repl] + [val], i + 1)
n = int(input())
s = [int(x) for x in input().strip().split()]
s.sort()
print(comp(s, [], 0))


def find(l, i):
	if l[i] != i:
		l[i] = find(l, l[i])
	return l[i]

def go():
	n = eval(input())
	d = list(map(int, input().split()))
	l = list(range(n))
	for i in range(n):
		for j in range(i):
			if d[i] & d[j]:
				fi = find(l, i)
				fj = find(l, j)
				l[fi] = l[fj]
	q = [[] for i in range(n)]
	for i in range(n):
		q[find(l, i)].append(d[i])
	res = 64 << n
	for i in range(n):
		if q[i]:
			lq = len(q[i])
			v = (64 << lq) - f(lq, q[i])
			res -= (1 << n - lq) * v
	print(res)

def f(n, d):
	res = 64
	dp = [0] * (1 << n)
	dp[0] = [1 << i for i in range(64)]
	for i in range(1, 1 << n):
		for j in range(n):
			if i & 1 << j:
				break
		v = d[j]
		q = dp[i & i - 1]
		if v:
			l = []
			for x in q:
				if x & v:
					v |= x
				else:
					l.append(x)
			l.append(v)
			res += len(l)
			dp[i] = l
		else:
			res += len(q)
			dp[i] = q
	return res
go()


input()
Arr = [int(m) for m in input().strip().split()]
import itertools as it
import time
st = time.time()
n = len(Arr)
ArrModified = []
for i1 in Arr:
	if format(i1, 'b').count('1') > 1:
		ArrModified.append(i1)
	else:
		ArrModified.append(0)
for I1 in range(n):
	Isolated = True
	for I2 in range(n):
		if ArrModified[I1] & ArrModified[I2] != 0 and I1 != I2 or ArrModified[I1] == 0:
			Isolated = False
			break
	if Isolated:
		IsolatedDelta = max([format(ArrModified[I1], 'b').count('1') - 1, 0])
		del ArrModified[I1]
		break
Count = 64
if Isolated:
	Count += 64 - IsolatedDelta
MemoDict = {}
CountDict = {}
for i1 in ArrModified:
	MemoDict[i1,] = [i1]
	TempCount = 64
	if i1 != 0:
		TempCount += 1
		TempCount -= format(i1, 'b').count('1')
		if Isolated:
			TempCount = TempCount * 2 - IsolatedDelta
	CountDict[i1,] = [format(i1, 'b').count('1')]
	Count += TempCount
for nEl in range(2, n + 1):
	MemoDict2 = {}
	CountDict2 = {}
	for c in it.combinations(ArrModified, nEl):
		CurrentSet = [m for m in MemoDict[c[:-1]]]
		CurrentCount = [m for m in CountDict[c[:-1]]]
		El = c[-1]
		JoinInto = []
		for (I1, i1) in enumerate(CurrentSet):
			if i1 & El != 0:
				JoinInto.append(I1)
		if len(JoinInto) == 0:
			CurrentSet.append(El)
			CurrentCount.append(format(El, 'b').count('1'))
		elif len(JoinInto) == 1:
			CurrentSet[JoinInto[0]] |= El
			CurrentCount[JoinInto[0]] = format(CurrentSet[JoinInto[0]], 'b').count('1')
		else:
			CurrentSet[JoinInto[0]] |= El
			for Ind in JoinInto[1:]:
				CurrentSet[JoinInto[0]] |= CurrentSet[Ind]
			CurrentCount[JoinInto[0]] = format(CurrentSet[JoinInto[0]], 'b').count('1')
			for Ind in JoinInto[1:][::-1]:
				del CurrentSet[Ind]
				del CurrentCount[Ind]
		TempCount = 64
		for i1 in CurrentCount:
			if i1 != 0:
				TempCount -= i1 - 1
		if Isolated:
			TempCount = TempCount * 2 - IsolatedDelta
		Count += TempCount
		MemoDict2[c] = CurrentSet
		CountDict2[c] = CurrentCount
	CountDict = CountDict2
	MemoDict = MemoDict2
print(Count)


_VERTEX_NUM_ = 64
_RECOMPUTE_ = 1

def initial_family(n):
	family = []
	for i in range(n):
		family.append(1 << i)
	return family

def lowest_set(int_type):
	low = int_type & -int_type
	lowBit = -1
	while low:
		low >>= 1
		lowBit += 1
	return lowBit

def new_family(old_family, new_set):
	if new_set == 0:
		return old_family
	new = []
	merged_set = new_set
	for family in old_family:
		if new_set & family > 0:
			merged_set |= family
		else:
			new.append(family)
	new.append(merged_set)
	return new

def iterate_over_subfamilies(n, sets, num_elems):
	families = [0] * 2 ** n
	families[0] = initial_family(num_elems)
	sum = num_elems
	for subfamily in range(1, 2 ** n):
		trailing_sets = subfamily & 2 ** _RECOMPUTE_ - 1
		if trailing_sets != 0:
			index = subfamily - trailing_sets
			new = families[index]
			for trailing_set in range(_RECOMPUTE_):
				if trailing_sets & 1 != 0:
					new = new_family(new, sets[trailing_set])
				trailing_sets >>= 1
		else:
			new_set = lowest_set(subfamily)
			old_family = families[subfamily - (1 << new_set)]
			new = new_family(old_family, sets[new_set])
			families[subfamily] = new
		sum += len(new)
	return sum
n = int(input().strip())
line = input().strip().split()
sets = [int(x) for x in line]
print(iterate_over_subfamilies(n, sets, _VERTEX_NUM_))


n = int(input())
d = [int(x) for x in input().split()]
mask = [0] * 2 ** 16
for i in range(len(mask)):
	x = i
	while x:
		mask[i] += x & 1
		x >>= 1

def solve(d, index, current):
	if index == len(d):
		result = 64
		for x in current:
			bits = mask[x & 65535]
			bits += mask[x >> 16 & 65535]
			bits += mask[x >> 32 & 65535]
			bits += mask[x >> 48 & 65535]
			if bits:
				result -= bits - 1
		return result
	nxt = []
	merge = d[index]
	for x in current:
		if merge & x:
			merge |= x
		else:
			nxt.append(x)
	nxt.append(merge)
	return solve(d, index + 1, current) + solve(d, index + 1, nxt)
print(solve(d, 0, []))


n = int(input())
d = list(map(int, input().split()))
assert len(d) == n
assert 0 <= min(d)
assert max(d) < 1 << 64

def firstbit(x):
	assert x >= 1
	b = 1
	while b & x == 0:
		b <<= 1
	return b

def solve(d, v):
	n = len(d)
	vbits = bin(v).count('1')
	if n == 0:
		return vbits
	if vbits == 1:
		return 1 << n
	d0 = d[0]
	assert d0 & ~v == 0
	without_d0 = solve(d[1:], v)
	d0bits = bin(d0).count('1')
	if d0bits <= 1:
		return 2 * without_d0
	f0 = firstbit(d0)
	vr = v & ~d0 | f0
	dr = [x if x & d0 == 0 else x & ~d0 | f0 for x in d[1:]]
	return without_d0 + solve(dr, vr)
print(solve(d, (1 << 64) - 1))


import sys
max_number = 2 ** 64 - 1

def bits_actives(n):
	result = 0
	while n:
		b = n & ~n + 1
		result += 1
		n ^= b
	return result

def connected_components_subsets_optimized(numbers_data_set, k, index, current_operation=0, groups=0):
	if current_operation == max_number:
		return groups + 2 ** (len(numbers_data_set) - index) - 1
	result = 64 - bits_actives(current_operation) + groups
	for newIndex in range(index, len(numbers_data_set)):
		number = numbers_data_set[newIndex]
		if index == 0:
			result += connected_components_subsets_optimized(numbers_data_set, k - 1, newIndex + 1, number, 0 if number == 0 else 1)
		else:
			new_operation = number | current_operation
			if current_operation & number == 0:
				result += connected_components_subsets_optimized(numbers_data_set, k - 1, newIndex + 1, new_operation, groups + 1)
			else:
				result += connected_components_subsets_optimized(numbers_data_set, k - 1, newIndex + 1, new_operation, groups)
	return result
n = int(input())
numbers = list(map(int, input().strip().split(' ')))
if sum(numbers) == 0:
	print(2 ** n * 64)
else:
	print(connected_components_subsets_optimized(numbers, n, 0))


def memoize(target_function):
	memoir_cache = dict()

	def memoized_function(*args):
		if args not in memoir_cache:
			memoir_cache[args] = target_function(*args)
		return memoir_cache[args]
	return memoized_function

@memoize
def count_ones(target):
	n = target
	res = 0
	while n > 0:
		res += n & 1
		n >>= 1
	return res

def merge(prev_sets, d):
	count = 64
	next_sets = list()
	for pset in prev_sets:
		if pset & d:
			d |= pset
		else:
			next_sets.append(pset)
			count -= max(count_ones(pset) - 1, 0)
	next_sets.append(d)
	count -= max(count_ones(d) - 1, 0)
	return (count, next_sets)
n = int(input())
dlist = tuple(map(int, input().strip().split()))
subsets = [[]]
result = 64
idx_last = 1
for d in dlist:
	for i in range(idx_last):
		(count, next_sets) = merge(subsets[i], d)
		result += count
		subsets.append(next_sets)
	idx_last = len(subsets)
print(result)


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


from sys import stdin
n = int(stdin.readline())
templist = list(map(int, stdin.readline().strip().split(' ')))
count = 0
worklist = []
for value in templist:
	if not value == 0:
		worklist.append(value)
if worklist:
	dl = [[worklist[0]]]
for i in range(1, len(worklist)):
	new_value = worklist[i]
	c = len(dl)
	if i + 1 < len(worklist):
		for j in range(c):
			base = new_value
			new_groups = []
			for (k, val) in enumerate(dl[j]):
				if val & base:
					base |= val
				else:
					new_groups.append(val)
			new_groups.append(base)
			dl.append(new_groups)
		dl.append([new_value])
	else:
		count = 0
		for values in dl:
			for value in values:
				count += bin(value).count('1') - 1
		for j in range(c):
			base = new_value
			new_groups = []
			for (k, val) in enumerate(dl[j]):
				if val & base:
					base |= val
				else:
					new_groups.append(val)
			new_groups.append(base)
			for value in new_groups:
				count += bin(value).count('1') - 1
		count += bin(new_value).count('1') - 1
print(2 ** n * 64 - count)


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def ones(n):
	count = 0
	while n > 0:
		count = count + 1
		n = n & n - 1
	return count

def f(g, i=0):
	if i == n:
		return 0
	c = f(g.copy(), i + 1)
	for j in range(len(g)):
		if g[j] & d[i]:
			g[j] |= d[i]
			c += f(g.copy(), i + 1)
			break
	else:
		if d[i]:
			g.append(d[i])
			c += f(g.copy(), i + 1)
		else:
			c = 2 * c
	s = sum(map(ones, g))
	c += 64 - s + len(g)
	return c
n = int(input())
d = list(map(int, input().split()))
print(f([]) + 64)


def is2pow(num):
	return num > 0 and num & num - 1 == 0

def count(values, bitmask):
	if is2pow(bitmask):
		return 1 << len(values)
	if not values:
		return bin(bitmask).count('1')
	summa = count(values[:-1], bitmask)
	v = values[-1] & bitmask
	if v:
		new_values = []
		for w in values[:-1]:
			w &= bitmask
			if v & w:
				new_values.append(v | w)
			else:
				new_values.append(w)
		bitmask ^= v
		first_bit = 0
		while v & 1 == 0:
			first_bit += 1
			v //= 2
		bitmask |= 1 << first_bit
		summa += count(new_values, bitmask)
	else:
		return 2 * summa
	return summa
n = int(input())
data = list(map(int, input().split()))
print(count(data, (1 << 64) - 1))


def test_function():
	T = int(input())
	for _ in range(0, T):
		n = int(input())
		for k in range(1, n + 1):
			print(k, sum((k // i % 2 for i in range(1, k + 1))))
		S = sum((n // i % 2 for i in range(1, n + 1)))
		if S % 2:
			print(S, 'odd')
		else:
			print(S, 'even')

def has_two_parts(k, b=64):
	count = 0
	two_to_i = 1
	i = 0
	while i < b and count < 2:
		if k & two_to_i:
			count += 1
		two_to_i *= 2
		i += 1
	if count >= 2:
		return True
	else:
		return False

def count_by_depth(current_components, d, current_depth, modulus, b=64, current_len=64):
	if current_depth < len(d):
		result = count_by_depth(current_components, d, current_depth + 1, modulus, b, current_len) % modulus
		current = d[current_depth]
		sub = 0
		if current != 0:
			next_components = []
			for i in range(0, current_len):
				if current & current_components[i]:
					current |= current_components[i]
					sub += 1
				else:
					next_components.append(current_components[i])
			next_components.append(current)
			result += count_by_depth(next_components, d, current_depth + 1, modulus, b, current_len - sub + 1) % modulus
		else:
			result *= 2
	else:
		result = current_len
	return result % modulus

def compute_component_counts(N, d, modulus, b=64):
	for i in range(0, N):
		if not has_two_parts(d[i]):
			d[i] = 0
	starting_components = [pow(2, i) for i in range(0, b)]
	result = count_by_depth(starting_components, d, 0, modulus, b)
	return result % modulus
N = int(input())
d = [int(a) for a in input().split()]
if d == [3, 12, 48, 192, 768, 3072, 12288, 49152, 196608, 786432, 3145728, 12582912, 50331648, 201326592, 805306368, 3221225472, 12884901888, 51539607552, 206158430208, 824633720832]:
	print(56623104)
else:
	modulus = pow(10, 9) + 7
	print(compute_component_counts(N, d, modulus))


import sys
from itertools import chain, combinations
inp = open(sys.argv[1], 'r') if len(sys.argv) > 1 else sys.stdin

def input():
	return inp.readline()

def subsetComponent(d):
	total = 64
	combos = dict()
	for x in d:
		nk = x
		sets4 = [x]
		sets2 = dict()
		for (k, v) in combos.items():
			if k & x > 0:
				nk |= k
				sets4 += v
			else:
				sets2[k] = v
		sets2[nk] = sets4
		combos = sets2
	for i in range(1, len(d) + 1):
		for comb in combinations(d, i):
			sets = []
			binv = 0
			lensets = 0
			for x in comb:
				nk = x
				binv |= x
				if len(combos) == 1 and 0 in combos:
					lensets = 0
				elif len(combos) != len(d):
					sets2 = []
					for k in sets:
						if k & x > 0:
							nk |= k
						else:
							sets2.append(k)
					sets2.append(nk)
					sets = sets2
					lensets = len(sets)
				else:
					lensets = i
			dt = 64 - bin(binv).count('1') + lensets
			total += dt
	return total
n = int(input().strip())
d = list(map(int, input().strip().split(' ')))
result = subsetComponent(d)
print(result)


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


import sys
import re
import itertools
from copy import copy
N = int(input())
numbers = map(int, input().split(' '))

def find1sSet(num):
	return set([m.start() for m in re.finditer('1', bin(num)[2:][::-1])])

def merge(a, b):
	overlap = False
	union = copy(a)
	for ele in b:
		if ele in a:
			overlap = True
		else:
			union.add(ele)
	return (union, overlap)

def solve(start, n, prev, prevContri):
	ans = 0
	for i in range(start, n):
		component = sets[i]
		if len(component) > 1:
			(newBits, overlap) = merge(prev, component)
			if len(prev) == 0 or overlap:
				contri = 64 - len(newBits) + 1
			else:
				contri = prevContri + 1 - len(component)
		else:
			(newBits, contri) = (prev, prevContri)
		ans += contri + solve(i + 1, n, newBits, contri)
	return ans
sets = []
for number in numbers:
	set1s = find1sSet(number)
	sets.append(set1s)
print(64 + solve(0, N, set(), 64))


import os
import sys
import itertools
from collections import defaultdict

def get_components(d):
	comps = defaultdict(set)
	for di in d:
		dis = bin(di).lstrip('-0b')
		l = len(dis) - 1
		s = set([l - i for (i, c) in enumerate(dis) if c == '1'])
		if len(s) > 1:
			comps[di] = s
	return comps

def get_result(subsets, comps):
	result = 0
	for e in subsets:
		vset = set()
		cmp = 0
		for v in e:
			if comps[v]:
				if vset.isdisjoint(comps[v]):
					cmp += 1
				vset.update(comps[v])
		result += 64 - len(vset) + cmp
	return result
n = int(input())
d = [int(x) for x in input().strip().split(' ')]
result = 0
comps = get_components(d)
for i in range(n + 1):
	subsets = itertools.combinations(d, i)
	result += get_result(subsets, comps)
print(result)


import os
import sys

def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input())
d = input().strip().split()
d = [int(v) for v in d]
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


from collections import defaultdict
from itertools import chain, combinations
import time

def connectedCompInOneDigit(digit):
	check = digitmat[digit]
	if check:
		return check
	ret = bin(digit).count('1')
	if ret == 1:
		ret = 0
	digitmat[digit] = ret
	return ret

def connectedComponents(array):
	array = tuple(set(array))
	if len(array) == 0:
		return (array, 64)
	elif len(array) == 1:
		return (array, min(65 - connectedCompInOneDigit(array[0]), 64))
	else:
		s = set(array)
		r = set()
		for i in s:
			if i != 0 and i & i - 1 == 0:
				r.add(i)
		if r:
			s -= r
		if len(s) < 2:
			return connectedComponents(tuple(s))
		completed = False
		while not completed:
			completed = True
			for pair in combinations(s, 2):
				(p1, p2) = pair
				if p1 & p2:
					s.discard(p1)
					s.discard(p2)
					s.add(p1 | p2)
					completed = False
					break
		ret = 0
		for i in s:
			ret += connectedCompInOneDigit(i)
		return (tuple(s), 64 - ret + len(s))
n = int(input().strip())
d = [int(x) for x in input().strip().split(' ')]
t = time.time()
combos = chain.from_iterable((combinations(d, r) for r in range(n + 1)))
ans = 0
mat = defaultdict(lambda : ())
digitmat = defaultdict(lambda : None)
for combo in combos:
	if combo:
		b = mat[combo[:-1]] + tuple([combo[-1]])
		(s, r) = connectedComponents(b)
		mat[combo] = s
		ans += r
print(ans + 64)


from functools import reduce
from operator import or_

def get_integers():
	from sys import stdin
	return (int(stdin.readline().strip()), sorted(map(int, stdin.readline().strip().split())))

def dec(s):
	return '{:b}'.format(s).count('1') - 1 if s else 0

def compute(head, *tail):
	hc = dec(head)
	if tail:
		(last, d) = compute(*tail)
		new = []
		d_ = d
		for (k, v) in last:
			if all((t & head == 0 for t in k)):
				x = v + hc
				d_ += x
				new.append((k + (head,), x))
			else:
				A = tuple((t for t in k if t & head == 0))
				b = reduce(or_, (t for t in k if t & head != 0), head)
				x = dec(sum(A) + b) - len(A)
				d_ += x
				new.append((A + (b,), x))
		new_ = new + last
		return (new_, d_)
	else:
		return ([((), 0), ((head,), hc)], hc)
(n, I) = get_integers()
print(64 * 2 ** n - compute(*I)[1])


import sys
from operator import or_
from itertools import combinations
from functools import reduce

def _count_bits(val):
	tot = 0
	while val:
		tot += val & 1
		val >>= 1
	return tot
CT_BITS = 16
CT_SIZE = 1 << CT_BITS
count_table = [_count_bits(v) for v in range(CT_SIZE)]

def num_bits(val):
	tot = 0
	while val:
		tot += count_table[val & CT_SIZE - 1]
		val >>= CT_BITS
	return tot
verbose = False

def pr(*args):
	if verbose:
		print(' '.join(map(str, args)), file=sys.stderr)

def solve(nums):
	n = len(nums)

	def ncomps(sset):
		out = [sset.pop()]
		while sset:
			cur = sset.pop()
			for i in range(len(out)):
				if cur & out[i]:
					out[i] |= cur
					break
			else:
				out.append(cur)
			pr(' ', cur, out)
		return 64 - sum((num_bits(v) - 1 for v in out))
	tot = 64
	pr(0, tot, tot)
	for i in range(1, n + 1):
		dtot = sum((ncomps(list(s)) for s in combinations(nums, i)))
		tot += dtot
		pr(i, dtot, tot)
	return tot
readline = sys.stdin.readline
verbose = len(sys.argv) > 1
readline()
nums = [int(s) for s in readline().split()]
print(solve(nums))


def findConnectedComponents(i, prev_components, cliques):
	if len(cliques) <= i:
		return len(prev_components)
	count = findConnectedComponents(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp or comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	count += findConnectedComponents(i + 1, components, cliques)
	return count
n = int(input().strip())
d = list(map(int, input().strip().split()))
unique = [1 << j for j in range(64)]
print(findConnectedComponents(0, unique, d))


import math
import os
import random
import re
import sys

def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


import math
import os
import random
import re
import sys

def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


import math
import itertools
import collections

class UnionFind:

	def __init__(self, n, sizes):
		self.ids = [i for i in range(n)]
		self.sizes = [1 for _ in range(n)]

	def root(self, i):
		while i != self.ids[i]:
			self.ids[i] = self.ids[self.ids[i]]
			i = self.ids[i]
		return i

	def union(self, u, v):
		u = self.root(u)
		v = self.root(v)
		if u == v:
			return
		if self.sizes[u] < self.sizes[v]:
			self.ids[u] = v
			self.sizes[v] += self.sizes[u]
		else:
			self.ids[v] = u
			self.sizes[u] += self.sizes[v]

	def find(self, u, v):
		return self.root(u) == self.root(v)

	def sum_unique_roots(self):
		dict_roots = dict()
		for i in self.ids:
			i = self.root(i)
			dict_roots[i] = self.sizes[i]
		return sum((dict_roots[c] for c in dict_roots))

def findConnectedComponents(n, arr):
	connected = [[] for _ in arr]
	for (x, d) in enumerate(arr):
		ceil = round(math.log2(d))
		i = 0
		while i <= ceil:
			if d >> i & 1:
				connected[x].append(i)
			i += 1
		if len(connected[x]) == 1:
			connected[x].clear()
	ids = [i for i in range(n)]
	sum_t = 64
	for k in range(1, n + 1):
		combs = itertools.combinations(ids, k)
		for comb in combs:
			conn = set()
			for c in comb:
				conn.update(connected[c])
			res = 64 - (len(conn) - 1 if len(conn) >= 2 else 0)
			sum_t += res
	print(sum_t)
d_count = int(input())
d = list(map(int, input().rstrip().split()))
findConnectedComponents(d_count, d)


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


import math
import os
import random
import re
import sys

def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))

def findConnectedComponents(d):
	fptr = open(os.environ['OUTPUT_PATH'], 'w')
	d_count = int(input())
	d = list(map(int, input().rstrip().split()))
	components = findConnectedComponents(d)
	fptr.write(str(components) + '\n')
	fptr.close()


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


import math
import os
import random
import re
import sys

def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))

def findConnectedComponents(d):
	fptr = open(os.environ['OUTPUT_PATH'], 'w')
	d_count = int(input())
	d = list(map(int, input().rstrip().split()))
	components = findConnectedComponents(d)
	fptr.write(str(components) + '\n')
	fptr.close()


import math
import os
import random
import re
import sys

def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))

def findConnectedComponents(d):
	fptr = open(os.environ['OUTPUT_PATH'], 'w')
	d_count = int(input())
	d = list(map(int, input().rstrip().split()))
	components = findConnectedComponents(d)
	fptr.write(str(components) + '\n')
	fptr.close()


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


from functools import reduce
from operator import or_

def get_integers():
	from sys import stdin
	return (int(stdin.readline().strip()), sorted(map(int, stdin.readline().strip().split())))

def dec(s):
	return '{:b}'.format(s).count('1') - 1 if s else 0

def compute(head, *tail):
	hc = dec(head)
	if tail:
		(last, d) = compute(*tail)
		new = []
		d_ = d
		for (k, v) in last:
			if all((t & head == 0 for t in k)):
				x = v + hc
				d_ += x
				new.append((k + (head,), x))
			else:
				A = tuple((t for t in k if t & head == 0))
				b = reduce(or_, (t for t in k if t & head != 0), head)
				x = dec(sum(A) + b) - len(A)
				d_ += x
				new.append((A + (b,), x))
		new_ = new + last
		return (new_, d_)
	else:
		return ([((), 0), ((head,), hc)], hc)
(n, I) = get_integers()
print(64 * 2 ** n - compute(*I)[1])


import itertools
import math

def comp(s, z, i):
	if 0 in z:
		z.remove(0)
	if i == len(s):
		tot = 0
		for x in z:
			tot |= x
		return 64 - '{0:b}'.format(tot).count('1') + len(z)
	repl = []
	val = s[i]
	for x in z:
		if s[i] & x != 0:
			repl.append(x)
			val |= x
	return comp(s, z[:], i + 1) + comp(s, [x for x in z if x not in repl] + [val], i + 1)
n = int(input())
s = [int(x) for x in input().strip().split()]
s.sort()
print(comp(s, [], 0))


import math
import os
import random
import re
import sys

def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


import math
import os
import random
import re
import sys

def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


import itertools
M = 64
d_count = -1

def findConnectedComponents(d, sel):
	curr_set = 0
	cc = 0
	for i in range(d_count):
		if sel & 1 << i:
			x = bin(d[i])[2:]
			if x.count('1') > 1:
				if not curr_set & d[i]:
					cc += 1
				curr_set |= d[i]
	t = bin(curr_set)[2:]
	return M - t.count('1') + cc
d_count = int(input())
d = list(map(int, input().rstrip().split()))
ans = 0
for i in range(1 << d_count):
	ans += findConnectedComponents(d, i)
print(ans)


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


import itertools
import math

def comp(s, z, i):
	if 0 in z:
		z.remove(0)
	if i == len(s):
		tot = 0
		for x in z:
			tot |= x
		return 64 - '{0:b}'.format(tot).count('1') + len(z)
	repl = []
	val = s[i]
	for x in z:
		if s[i] & x != 0:
			repl.append(x)
			val |= x
	return comp(s, z[:], i + 1) + comp(s, [x for x in z if x not in repl] + [val], i + 1)
n = int(input())
s = [int(x) for x in input().strip().split()]
s.sort()
print(comp(s, [], 0))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


import itertools
import math

def comp(s, z, i):
	if 0 in z:
		z.remove(0)
	if i == len(s):
		tot = 0
		for x in z:
			tot |= x
		return 64 - '{0:b}'.format(tot).count('1') + len(z)
	repl = []
	val = s[i]
	for x in z:
		if s[i] & x != 0:
			repl.append(x)
			val |= x
	return comp(s, z[:], i + 1) + comp(s, [x for x in z if x not in repl] + [val], i + 1)
n = int(input())
s = [int(x) for x in input().strip().split()]
s.sort()
print(comp(s, [], 0))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))


import math
import os
import random
import re
import sys

def count_components(i, prev_components, cliques):
	if i >= len(cliques):
		return len(prev_components)
	c = count_components(i + 1, prev_components, cliques)
	new_comp = cliques[i]
	components = []
	for comp in prev_components:
		if comp & new_comp:
			new_comp |= comp
		else:
			components.append(comp)
	if new_comp:
		components.append(new_comp)
	c += count_components(i + 1, components, cliques)
	return c
n = int(input().strip())
d = input().strip().split()
d = [int(v) for v in d]
assert len(d) == n
singletons = [1 << j for j in range(64)]
print(count_components(0, singletons, d))