def kth_permutation(n: int, k: int) -> str:
factorials = [1]
digits = ["1"]
for i in range(1, n):
factorials.append(factorials[-1] * i)
digits.append(str(i + 1))
output = []
k -= 1
for i in range(n - 1, -1, -1):
# index = k // factorials[i]
# k = k - idx * factorials[i]
index, k = divmod(k, factorials[i])
output.append(digits[index])
del digits[index]
return "".join(output)