Permutations IV

Return the k-th lexicographically-sorted permutation of 1..n whose adjacent elements alternate parity (no two consecutive odds or evens). With n up to 100 and k up to 1e15, the core challenge is to count valid permutations efficiently (DP/combinatorics) and use those counts to construct the k-th sequence without enumerating all permutations.