# 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

MTAKMjIyMjIyMjIyMjIyMjIyMjIyMjI=

10
22222222222222222222