The set `[1,2,3,...,`

contains a total of *n*]*n*! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for *n* = 3:

`"123"`

`"132"`

`"213"`

`"231"`

`"312"`

`"321"`

Given *n* and *k*, return the *k*^{th} permutation sequence.

**Note:**

- Given
*n*will be between 1 and 9 inclusive. - Given
*k*will be between 1 and*n*! inclusive.

**Example 1:**

Input:n = 3, k = 3Output:"213"

**Example 2:**

Input:n = 4, k = 9Output:"2314"

class Solution: def getPermutation(self, n: int, k: int) -> str: res, nums = "", list(range(1, n + 1)) k -= 1 for n in range(n, 0, -1): index, k = divmod(k, math.factorial(n-1)) res += str(nums.pop(index)) return res