import itertools
import time

true = True
false= False

def bf(width,height,g):
        row = [(0,1)] * width
        col = (itertools.product(*row) for _ in range(height))
        a = machine(list(itertools.product(*col)),g)
        return a

def machine(x,g):
        j=0
        for i,k in enumerate(x):
                if tran(x[i][0][0],x[i][0][1],x[i][1][0],x[i][1][1]) == g[0][0]:
                        if tran(x[i][-1][0],x[i][-1][1],x[i][-2][0],x[i][-2][1]) == g[-1][0]:
                                if tran(x[i][0][-2],x[i][1][-2],x[i][1][-1],x[i][0][-1]) == g[0][-1]:
                                        if tran(x[i][-2][-1],x[i][-2][-2],x[i][-1][-2],x[i][-1][-1]) == g[-1][-1]:
                                                if tran(x[i][1][1],x[i][1][2],x[i][2][1],x[i][2][2]) == g[1][1]:
                                                        if nk(k) == g:
                                                                j += 1
        return j

def tran(a,b,c,d):
        if a+b+c+d == 1:
                return 1
        else:
                return 0

def nk(arr):
    width = len(arr[0])
    height = len(arr)
    arr_new = [[0 for x in range(0)] for y in range(height-1)]
    for x in xrange(0,height-1):
        for y in xrange(0,width-1):
            if arr[x][y] + arr[x][y+1] + arr[x+1][y] + arr[x+1][y+1] == 1:
                    arr_new[x].append(1)

            else:
                    arr_new[x].append(0)
    return arr_new

def answer(g):
        start = time.time()
        width = len(g[0]) + 1
        height = len(g) + 1
        print bf(width,height,g)
        print "Time : ", (time.time()-start)