[C++/Python] Combinatrics and checking for overflow
IntuitionWhen you chose a digit A, count total possible permutations of remaining values. Permutations of even values * Permutations of odd valuesIf the count i
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
When you chose a digit A, count total possible permutations of remaining values. `Permutations of even values` * `Permutations of odd values`

If the count is not enough to reach k, skip to the next smallest available B that is greater than A, so on and so forth.

Permutations of N digits = N! = 1 * 2 * 3 ... * N

Since k is 10^15, do not need to call larger than factorial(18).

If parameter to factorial is larger or equal to 18, or the product of the two factorials exceed `long long` (using `__builtin_mul_overflow`), just use the current digit as it will be within the range to obtain `k`.

# Code
```cpp []
class Solution {
public:
    using ll = long long;
    unordered_map<int, ll> fac;
    ll mod = 1e9 + 7;
    tuple<bool, ll> factorial(int i) { // left result is true if overflows, right is factorial of i
        if (i == 0) return {true, 0L};
        if (i == 1) return {true, 1L};
        if (i >= 18) return {false, 0L};
        if (fac.find(i) == end(fac)) {
            ll ans = i * get<1>(factorial(i-1));
            ans %= mod;
            fac[i] = ans;
        }        
        return {true, fac[i]};
    }

    vector<int> permute(int n, long long k) {
        // numbers are sorted in lexicographical order
        vector<int> numbers;
        for (int i = 0; i < n; ++i) {
            numbers.push_back(i + 1);
        }

        vector<int> ans;
        if (n % 2 == 0) {
            return dfs(numbers, k-1, 2);
        } else {
            return dfs(numbers, k-1, 1);
        }
    }

    /*
    ParityState
    0 -> even
    1 -> odd
    2 -> can be either even or odd (this is for the first digit even total count is even)
    */
    vector<int> dfs(vector<int> numbers, ll k, int parityState) {
        int n = numbers.size();
        if (n == 0) {
            return {};
        }

        ll curr = 0;
        for (int i = 0; i < n; ++i) {
            if (parityState == 2 || numbers[i] % 2 == parityState) {
                int count = n-1;
                ll perm = 0;

                // check for overflow
                // hack since k < 10^15 so if overflow you can ensure k is in the range between
                // curr - perm <= k < curr
                auto [notOverFlow1, c1] = factorial(count/2);
                auto [notOverFlow2, c2] = factorial(count/2 + 1);
                ll first = c1, second = count % 2 == 0 ? c1 : c2, result;
                if (!__builtin_mul_overflow(first, second, &result)) {
                    perm = first * second;
                }

                perm = max(1LL, perm);
                curr += perm;
                
                if (!notOverFlow1 || !notOverFlow2 || __builtin_mul_overflow(first, second, &result) || k < curr) {
                    int ans = numbers[i];
                    numbers.erase(begin(numbers) + i);
                    int nextP = ans % 2 == 0 ? 1 : 0;
                    auto res = dfs(numbers, k - curr + perm, nextP);
                    res.insert(res.begin(), ans);
                    return res;
                }
            }
        }            
        
        return {};
    }
};
```

```python []
class Solution:
    def permute(self, n: int, k: int) -> List[int]:
        numbers = [i+1 for i in range(n)]
        return self.dfs(numbers, k-1, 2 if n % 2 == 0 else 1)

    def dfs(self, numbers, k, parityState):
        n = len(numbers)
        if n == 0:
            return []
        
        curr = 0
        for i in range(n):
            num = numbers[i]
            if parityState == 2 or numbers[i] % 2 == parityState:
                # count number of permutations possible starting with numbers[i]
                count, perm = n-1, 0
                first = factorial(count//2)
                second = factorial((count//2) if count % 2 == 0 else (count//2 + 1))
                perm = max(1, first * second)

                if k < (curr + perm):
                    numbers.remove(num)
                    nextP = 1 if num % 2 == 0 else 0
                    return [num] + self.dfs(numbers, k - curr, nextP)
                
                curr += perm
        
        return []
```


['C++', 'Python3']