#
# Finding Comb(n,k) using Dynamic Programming
#
def fn():
      n = 6
      k = 4
      rows = n
      cols = k
      C = [[0 for _ in range(rows+1)] for _ in range(rows+1)]
      C[0][0] = 1
      for i in range(1, n+1):
          for j in range(0, i+1):
              if 0 == j or i == j:
                 C[i][j] = 1
              C[i][j] = C[i-1][j-1] + C[i-1][j]
      for i in range(0, n+1):
          for j in range(0, i+1):
              print(C[i][j],end=" ")
          print()
      print(C[n][k])

fn()

IwojIEZpbmRpbmcgQ29tYihuLGspIHVzaW5nIER5bmFtaWMgUHJvZ3JhbW1pbmcKIwpkZWYgZm4oKToKICAgICAgbiA9IDYKICAgICAgayA9IDQKICAgICAgcm93cyA9IG4KICAgICAgY29scyA9IGsKICAgICAgQyA9IFtbMCBmb3IgXyBpbiByYW5nZShyb3dzKzEpXSBmb3IgXyBpbiByYW5nZShyb3dzKzEpXQogICAgICBDWzBdWzBdID0gMQogICAgICBmb3IgaSBpbiByYW5nZSgxLCBuKzEpOgogICAgICAgICAgZm9yIGogaW4gcmFuZ2UoMCwgaSsxKToKICAgICAgICAgICAgICBpZiAwID09IGogb3IgaSA9PSBqOgogICAgICAgICAgICAgICAgIENbaV1bal0gPSAxCiAgICAgICAgICAgICAgQ1tpXVtqXSA9IENbaS0xXVtqLTFdICsgQ1tpLTFdW2pdCiAgICAgIGZvciBpIGluIHJhbmdlKDAsIG4rMSk6CiAgICAgICAgICBmb3IgaiBpbiByYW5nZSgwLCBpKzEpOgogICAgICAgICAgICAgIHByaW50KENbaV1bal0sZW5kPSIgIikKICAgICAgICAgIHByaW50KCkKICAgICAgcHJpbnQoQ1tuXVtrXSkKCmZuKCkK