





from __future__ import annotations



def 				lowerCAmelCase_ (							A_):

    # preprocessing the first row
    for i in range(1    ,len(matrix[0])):
        matrix[0][i] += matrix[0][i - 1]

    # preprocessing the first column
    for i in range(1    ,len(A_)):
        matrix[i][0] += matrix[i - 1][0]

    # updating the path cost for current position
    for i in range(1    ,len(A_)):
        for j in range(1    ,len(matrix[0])):
            matrix[i][j] += min(matrix[i - 1][j]    ,matrix[i][j - 1])

    return matrix[-1][-1]


if __name__ == "__main__":
   import doctest

   doctest.testmod()








def 				lowerCAmelCase_ (							A_    ,A_):
    UpperCamelCase__:	str					=     [1]
    for i in range(2    ,A_):
        factorials.append(factorials[-1] * i)
    assert 0 <= k < factorials[-1] * n, "k out of bounds"

    UpperCamelCase__:	Optional[int]					=     []
    UpperCamelCase__:	Optional[Any]					=     list(range(A_))

    # Find permutation
    while factorials:
        UpperCamelCase__:	Dict					=     factorials.pop()
        UpperCamelCase__				, UpperCamelCase__:	Optional[int]					=     divmod(A_    ,A_)
        permutation.append(elements[number])
        elements.remove(elements[number])
    permutation.append(elements[0])

    return permutation


if __name__ == "__main__":
   import doctest

   doctest.testmod()

