Permutation Sequence

The set [1, 2, 3, …, n] contains a total of n! unique permutations.

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

1. “123”
2. “132”
3. “213”
4. “231”
5. “312”
6. “321”

Given n and k, return the kth permutation sequence.

Input Format

The input should consist of two space-separated integers, n, and k.

Output Format

The output should consist of a single line, the kth permutation sequence.

Example 1:

Input:
    3 3
Output:
    213

Example 2:

Input:
    4 9
Output:
    2314

Example 3:

Input:
    3 1
Output:
    123

Constraints:

• 1 <= n <= 9
• 1 <= k <= n!