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