output_description: Print the sum of the scores, modulo 10^9 + 7.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      H W K
attempt: import sys
  from collections import defaultdict
  
  
  def calc5(all_nodes, H, W, K):
      while K != 0:
          next_nodes = dict()
          for k, v in all_nodes.items():
              if k[0] + 1 <= H + 1:
                  k0 = k[0] + 1
                  s = (k[0] + 1) * k[1] + k[2]
                  if (k0, k[1], s) in next_nodes:
                      next_nodes[(k0, k[1], s)] += v * (H + 1 - k[0])
                  else:
                      next_nodes[(k0, k[1], s)] = v * (H + 1 - k[0])
              if k[1] + 1 <= W + 1:
                  k1 = k[1] + 1
                  s = (k[1] + 1) * k[0] + k[2]
                  if (k[0], k1, s) in next_nodes:
                      next_nodes[(k[0], k1, s)] += v * (W + 1 - k[1])
                  else:
                      next_nodes[(k[0], k1, s)] = v * (W + 1 - k[1])
  
          all_nodes = next_nodes
          K -= 1
      print(sum([k[2] * v for k, v in all_nodes.items()]))
      # a = ( sum([ k[2]*v for k,v in all_nodes.items()]) )
  
  
  def main5(H, W, K):
      all_nodes = {}
      all_nodes[(1, 1, 0)] = 1
      calc5(all_nodes, H, W, K)
  
  
  if __name__ == "__main__":
      # H,W,K = sys.argv[1:]
      tmp = input()
      H, W, K = tmp.split()
      main5(int(H), int(W), int(K))
  
problem_description: Statement
  
  There is a rectangular sheet of paper with height H+1 and width W+1. We
  introduce an xy-coordinate system so that the four corners of the sheet are
  (0, 0), (W + 1, 0), (0, H + 1) and (W + 1, H + 1).
  
  This sheet can be cut along the lines x = 1,2,...,W and the lines y =
  1,2,...,H. Consider a sequence of operations of length K where we choose K of
  these H + W lines and cut the sheet along those lines one by one in some
  order.
  
  Let the score of a cut be the number of pieces of paper that exist just after
  the cut. The score of a sequence of operations is the sum of the scores of all
  of the K cuts.
  
  Find the sum of the scores of all possible sequences of operations of length
  K. Since this value can be extremely large, print the number modulo 10^9 + 7.
samples: [{"input": "2 1 2", "output": "34\n    \n\nLet x_1, y_1 and y_2 denote the cuts along the lines x = 1, y = 1 and y = 2,\nrespectively. The six possible sequences of operations and the score of each\nof them are as follows:\n\n  * y_1, y_2: 2 + 3 = 5\n  * y_2, y_1: 2 + 3 = 5\n  * y_1, x_1: 2 + 4 = 6\n  * y_2, x_1: 2 + 4 = 6\n  * x_1, y_1: 2 + 4 = 6\n  * x_1, y_2: 2 + 4 = 6\n\nThe sum of these is 34.\n\n* * *"}, {"input": "30 40 50", "output": "616365902\n    \n\nBe sure to print the sum modulo 10^9 + 7."}]