# 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"