L=len
def R(n,k):
 q=[(n,[])]
 for n,p in q:
  if(k==L(p))>n:yield tuple(sorted(p))
  elif k>L(p):
   for j in range(n):q+=(n+~j,p+[j+1]),
def M(e,t,I,l):
 q=[(l,{*I},[])]
 for l,I,m in q:
  if l:q+=[(l[1:],I-{i},m+[(i,l[0])])for i in I if e[i]+l[0]<=t[i]]
  else:yield m
def f(t):
 q,r=[([0]*L(t),[])],0
 for e,v in q:
  if e==t:r+=1
  elif l:=[i for i,a in enumerate(e)if a<t[i]]:
   i,*I=l
   for j in range(L(I)):
    for l in{*R(t[i]-e[i],j+1)}:
     for U in map(eval,{str(sorted(K))for K in M(e,t,I,[*l])}):
      E=[*e];E[i]=t[i]
      for x,y in U:E[x]+=y
      q+=(E,v+[(i,x,y)for x,y in U]),
 return r
 
import re
s1 = """
[6,2]           | 0
[5,3,2]         | 1
[3,3,1,1]       | 3
[4,3,1,1,1]     | 6
[4,2,1,1,1,1]   | 10
[1,1,1,1,1,1]   | 15
[3,2,2,2,1]     | 15
[2,2,2,2,2]     | 22
[7,6,5,4,3,2,1] | 7757
"""
for i in filter(None, s1.split('\n')):
	a, b = re.split('\s+\|\s+', i)
	assert f(eval(a)) == int(b)
 
print('tests passed')

TD1sZW4KZGVmIFIobixrKToKIHE9WyhuLFtdKV0KIGZvciBuLHAgaW4gcToKICBpZihrPT1MKHApKT5uOnlpZWxkIHR1cGxlKHNvcnRlZChwKSkKICBlbGlmIGs+TChwKToKICAgZm9yIGogaW4gcmFuZ2Uobik6cSs9KG4rfmoscCtbaisxXSksCmRlZiBNKGUsdCxJLGwpOgogcT1bKGwseypJfSxbXSldCiBmb3IgbCxJLG0gaW4gcToKICBpZiBsOnErPVsobFsxOl0sSS17aX0sbStbKGksbFswXSldKWZvciBpIGluIEkgaWYgZVtpXStsWzBdPD10W2ldXQogIGVsc2U6eWllbGQgbQpkZWYgZih0KToKIHEscj1bKFswXSpMKHQpLFtdKV0sMAogZm9yIGUsdiBpbiBxOgogIGlmIGU9PXQ6cis9MQogIGVsaWYgbDo9W2kgZm9yIGksYSBpbiBlbnVtZXJhdGUoZSlpZiBhPHRbaV1dOgogICBpLCpJPWwKICAgZm9yIGogaW4gcmFuZ2UoTChJKSk6CiAgICBmb3IgbCBpbnsqUih0W2ldLWVbaV0saisxKX06CiAgICAgZm9yIFUgaW4gbWFwKGV2YWwse3N0cihzb3J0ZWQoSykpZm9yIEsgaW4gTShlLHQsSSxbKmxdKX0pOgogICAgICBFPVsqZV07RVtpXT10W2ldCiAgICAgIGZvciB4LHkgaW4gVTpFW3hdKz15CiAgICAgIHErPShFLHYrWyhpLHgseSlmb3IgeCx5IGluIFVdKSwKIHJldHVybiByCiAKaW1wb3J0IHJlCnMxID0gIiIiCls2LDJdICAgICAgICAgICB8IDAKWzUsMywyXSAgICAgICAgIHwgMQpbMywzLDEsMV0gICAgICAgfCAzCls0LDMsMSwxLDFdICAgICB8IDYKWzQsMiwxLDEsMSwxXSAgIHwgMTAKWzEsMSwxLDEsMSwxXSAgIHwgMTUKWzMsMiwyLDIsMV0gICAgIHwgMTUKWzIsMiwyLDIsMl0gICAgIHwgMjIKWzcsNiw1LDQsMywyLDFdIHwgNzc1NwoiIiIKZm9yIGkgaW4gZmlsdGVyKE5vbmUsIHMxLnNwbGl0KCdcbicpKToKCWEsIGIgPSByZS5zcGxpdCgnXHMrXHxccysnLCBpKQoJYXNzZXJ0IGYoZXZhbChhKSkgPT0gaW50KGIpCgpwcmludCgndGVzdHMgcGFzc2VkJyk=