def gen_masks(h):
	# Cache numbers with one bit.
	ones = [1 << x for x in range(h*2)]

	trans = []	# AND masks for applying the transform.
	init = int(("11"+"0"*(h-2))*2, 2)
	for i in range(h-1): trans.append(init >> i)

	return (ones, trans)


def col(g, i):
	return [x[i] for x in g]


def get_preimages(col, o, t, bound=None):
	# Obtains the valid preimages.
	valid = {}
	branches = 0
	h = len(col) + 1

	if bound == None:
		for n in range(o[-1]*2):	# All possible preimages.
			if n in o: continue
			for i,m in enumerate(t):
				if col[i] != ((n & m) in o): break
			else:
				if n not in valid: valid[n] = 0
				valid[n] += 1
		# Dictionary not necessary for first run, but keep for consistentcy.
		branches = sum(valid.values())	
	else:
		for b in bound.keys():	# Preimages bound by the last valid columns.
			branches -= bound[b]
			for x in range(1 << h):
				n = x + b
				for i,m in enumerate(t): 
					if col[i] != ((n & m) in o): break
				else:
					if n not in valid: valid[n] = 0
					# Keep track of what to remove later. Carrythrough.
					valid[n] += bound[b]	
					branches += bound[b]

	new_bound = dict()
	# AND mask for extracting second column. (Last 4 bits)
	mask = int("0"*h+"1"*h, 2) 
	for n in valid:  
		a = (n & mask) << h
		if a not in new_bound: new_bound[a] = 0
		new_bound[a] += valid[n]

	return (branches, new_bound)


def solution(g):
	o, t = gen_masks(len(g)+1)

	count, bound = get_preimages(col(g, 0), o, t)
	for i in range(1, len(g[0])):
		c, bound = get_preimages(col(g, i), o, t, bound)
		count += c
	
	print("Count", count)
	return count


solution([[True, False, True], [False, True, False], [True, False, True]])
solution([
	[True, False, True, False, False, True, True, True], 
	[True, False, True, False, False, False, True, False], 
	[True, True, True, False, False, False, True, False], 
	[True, False, True, False, False, False, True, False], 
	[True, False, True, False, False, True, True, True]])
solution([[True, True, False, True, False, True, False, True, True, False], [True, True, False, False, False, False, True, True, True, False], [True, True, False, False, False, False, False, False, False, True], [False, True, False, False, False, False, True, True, False, False]])
solution([
	[True, False, True, False, False, True, True, True, True, False, True, False, False, True, True, True], 
	[True, False, True, False, False, False, True, False, True, False, True, False, False, False, True, False], 
	[True, True, True, False, False, False, True, False, True, True, True, False, False, False, True, False], 
	[True, False, True, False, False, False, True, False, True, False, True, False, False, False, True, False], 
	[True, False, True, False, False, True, True, True, True, False, True, False, False, True, True, True]])