# -*- coding: utf-8 -*- 

class PermanentComputation:
  def compute(_, matrix):
    m = [[int(v) for v in m.split()] for m in matrix]

    memo = [{} for _ in m]
    def rec(j, idx):
      if j+1 == len(m):
        i, = idx
        return m[j][i]
      else:
        if idx in memo[j]:
          return memo[j][idx]
        sum = 0
        for id,i in enumerate(idx):
          if m[j][i] <> 0:
            sum += m[j][i] * rec(j+1, idx[:id]+idx[id+1:])
        sum %= 10000
        memo[j][idx] = sum
        return sum
    return rec(0, tuple(range(len(m))))

if __name__ == "__main__":
  x = PermanentComputation()
  print x.compute( ("1 2 3", "4 5 6", "7 8 9") )
  print x.compute(
    ("1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
     "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
     "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
     "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
     "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
     "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
     "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
     "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
     "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
     "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
     "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
     "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
     "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
     "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
     "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1",
     "1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1"))