# Python program for OEIS A262239
# Michael S. Branicky, Dec 31 2021

# A262239		Number of (n+3)X(4+3) 0..1 arrays with each row and column divisible by 11, read as a binary number with top and left being the most significant bits.		0
data = [12, 31, 238, 1306, 10747, 77490, 778464, 4345849, 31098659, 251964601, 2327886878]

# (Python)
from itertools import product

candrows = [bin(m)[2:].zfill(7) for m in range(0, 2**7, 11)]
   
# hardcoded backtracking; first n-1 rows have no constraints
def a(n):
    if n == 1:
        return 12
    count = 0
    candcols = [bin(m)[2:].zfill(n+3) for m in range(0, 2**(n+3), 11)]
    prefixes = set(c[:n+3-tail] for tail in range(4) for c in candcols)
    for arr in product(candrows, repeat=n-1):
        cols = list("".join(arr[i][j] for i in range(n-1)) for j in range(7))
        for rowm4 in candrows:
            if not all(cols[j]+rowm4[j] in prefixes for j in range(7)):
                continue
            for rowm3 in candrows:
                if not all(cols[j]+rowm4[j]+rowm3[j] in prefixes for j in range(7)):
                    continue
                for rowm2 in candrows:
                    if not all(cols[j]+rowm4[j]+rowm3[j]+rowm2[j] in prefixes for j in range(7)):
                        continue  
                    for rowm1 in candrows:
                        if not all(cols[j]+rowm4[j]+rowm3[j]+rowm2[j]+rowm1[j] in prefixes for j in range(7)):
                            continue      
                        count += 1
    return count

print([a(n) for n in range(1, 6)]) # ~~~~
print(data)
print()

from time import time
time0 = time()

for n in range(1, 10):
    an = a(n)
    print(n, an, an == data[n-1], time()-time0)