# factorial table
FAC = [1]
def gen_fac(n)
n.times do |i|
FAC << FAC[i]*(i+1)
end
end
# generates a mask such that it is matched by each string that matches m and n
def diff_mask(m,n)
q = m.dup
m.size.times do |i|
c1 = m[i]
c2 = n[i]
if c1=="0"&&c2=="1"||c1=="1"&&c2=="0"
return nil
elsif c1=='2'
q[i] = c2
elsif c2 == '2'
q[i] = c1
end
end
q
end
# counts the number of possible balanced strings matching the mask
def count_mask(m)
n = m.size
c0 = n/2-m.count("0")
c1 = n/2-m.count("1")
c2 = c0+c1
if c0>n/2 || c1>n/2
0
else
FAC[c2]/(FAC[c0]*FAC[c2-c0])
end
end
# union masks of cn masks from m.size masks
def mask_diff_combinations(m,n=1,s=m.size,diff1='2'*m[0].size,j=-1,&b)
(j+1..s-1).each do |i|
diff2 = diff_mask(diff1,m[i])
next if !diff2
mask_diff_combinations(m,n+1,s,diff2,i,&b) if n<s
yield diff2,n
end
end
# counts the number of balanced strings matched by at least one mask
def count_n_masks(m)
sum = 0
mask_diff_combinations(m) do |mask,i|
sum += i%2==1 ? count_mask(mask) : -count_mask(mask)
end
sum
end
time = Time.now
# parse input
d = STDIN.each_line.map do |line|
line.chomp.strip
end
d.delete_if(&:empty?)
d.shift
# generate factorial table
gen_fac([d.size,d[0].size].max+1)
# count masks
puts "number of matches: #{count_n_masks(d)}"
puts "took #{Time.now-time} s"
IyBmYWN0b3JpYWwgdGFibGUKRkFDID0gWzFdCmRlZiBnZW5fZmFjKG4pCiAgbi50aW1lcyBkbyB8aXwKICAgIEZBQyA8PCBGQUNbaV0qKGkrMSkKICBlbmQKZW5kCgojIGdlbmVyYXRlcyBhIG1hc2sgc3VjaCB0aGF0IGl0IGlzIG1hdGNoZWQgYnkgZWFjaCBzdHJpbmcgdGhhdCBtYXRjaGVzIG0gYW5kIG4KZGVmIGRpZmZfbWFzayhtLG4pCiAgcSA9IG0uZHVwCiAgbS5zaXplLnRpbWVzIGRvIHxpfAogICAgYzEgPSBtW2ldCiAgICBjMiA9IG5baV0KICAgIGlmIGMxPT0iMCImJmMyPT0iMSJ8fGMxPT0iMSImJmMyPT0iMCIKICAgICAgcmV0dXJuIG5pbAogICAgZWxzaWYgYzE9PScyJwogICAgICBxW2ldID0gYzIKICAgIGVsc2lmIGMyID09ICcyJwogICAgICBxW2ldID0gYzEKICAgIGVuZAogIGVuZAogIHEKZW5kCgojIGNvdW50cyB0aGUgbnVtYmVyIG9mIHBvc3NpYmxlIGJhbGFuY2VkIHN0cmluZ3MgbWF0Y2hpbmcgdGhlIG1hc2sKZGVmIGNvdW50X21hc2sobSkKICBuID0gbS5zaXplCiAgYzAgPSBuLzItbS5jb3VudCgiMCIpCiAgYzEgPSBuLzItbS5jb3VudCgiMSIpCiAgYzIgPSBjMCtjMQogIGlmIGMwPm4vMiB8fCBjMT5uLzIKICAgIDAKICBlbHNlCiAgICBGQUNbYzJdLyhGQUNbYzBdKkZBQ1tjMi1jMF0pCiAgZW5kCmVuZAoKIyB1bmlvbiBtYXNrcyBvZiBjbiBtYXNrcyBmcm9tIG0uc2l6ZSBtYXNrcwpkZWYgbWFza19kaWZmX2NvbWJpbmF0aW9ucyhtLG49MSxzPW0uc2l6ZSxkaWZmMT0nMicqbVswXS5zaXplLGo9LTEsJmIpCiAgKGorMS4ucy0xKS5lYWNoIGRvIHxpfAogICAgZGlmZjIgPSBkaWZmX21hc2soZGlmZjEsbVtpXSkKICAgIG5leHQgaWYgIWRpZmYyCiAgICBtYXNrX2RpZmZfY29tYmluYXRpb25zKG0sbisxLHMsZGlmZjIsaSwmYikgaWYgbjxzCiAgICB5aWVsZCBkaWZmMixuCiAgZW5kCmVuZAoKIyBjb3VudHMgdGhlIG51bWJlciBvZiBiYWxhbmNlZCBzdHJpbmdzIG1hdGNoZWQgYnkgYXQgbGVhc3Qgb25lIG1hc2sKZGVmIGNvdW50X25fbWFza3MobSkKICBzdW0gPSAwCiAgbWFza19kaWZmX2NvbWJpbmF0aW9ucyhtKSBkbyB8bWFzayxpfAogICAgc3VtICs9IGklMj09MSA/IGNvdW50X21hc2sobWFzaykgOiAtY291bnRfbWFzayhtYXNrKQogIGVuZAogIHN1bQplbmQKCgp0aW1lID0gVGltZS5ub3cKCiMgcGFyc2UgaW5wdXQKZCA9IFNURElOLmVhY2hfbGluZS5tYXAgZG8gfGxpbmV8CiAgbGluZS5jaG9tcC5zdHJpcAplbmQKZC5kZWxldGVfaWYoJjplbXB0eT8pCmQuc2hpZnQKCiMgZ2VuZXJhdGUgZmFjdG9yaWFsIHRhYmxlCmdlbl9mYWMoW2Quc2l6ZSxkWzBdLnNpemVdLm1heCsxKQoKIyBjb3VudCBtYXNrcwpwdXRzICJudW1iZXIgb2YgbWF0Y2hlczogI3tjb3VudF9uX21hc2tzKGQpfSIKcHV0cyAidG9vayAje1RpbWUubm93LXRpbWV9IHMi