Alternative Permutations

Johnny wrote a permutation to binary search tree (BST) converter. Given a permutation $(\pi_1, \pi_2, \ldots, \pi_n)$, it assigns $\pi_1$ to the root. From the numbers in $(\pi_2, \pi_3, \ldots, \pi_n)$ that are smaller than $\pi_1$, it recursively builds a BST, keeping their original order, and attaches it as the left subtree of the root. Symmetrically, from the numbers larger than $\pi_1$, it builds a BST and attaches it as the right subtree. To Johnny's surprise, different permutations can produce the same BST. For instance, $(2, 3, 1)$ and $(2, 1, 3)$ produce the same BST. Surprised by this fact, he defined Johnny's Numbers $J_k$: the $k$-th Johnny's Number is the smallest $n$ such that some BST on $n$ nodes labelled $1, 2, \ldots, n$ can be obtained from exactly $k$ different permutations of $1, 2, \ldots, n$. Studying Johnny's Numbers is hard, and interest in them is fading. Help Johnny compute $J_k$ for a given $k$.

The first line contains a natural number $k$ ($1 \le k \le 10^{11}$).

On the first line, print a positive integer $J_k$, provided that it exists and is at most $5000$. On the second line, print the $J_k$ integers of the lexicographically smallest generating permutation among the $k$ permutations. Otherwise, that is, if $J_k$ does not exist or is larger than $5000$, print the word NIE (Polish for 'no').

The tree having exactly eight generating permutations is shown below: All permutations generating that tree are: $(2, 1, 4, 3, 5)$, $(2, 1, 4, 5, 3)$, $(2, 4, 1, 3, 5)$, $(2, 4, 1, 5, 3)$, $(2, 4, 3, 1, 5)$, $(2, 4, 3, 5, 1)$, $(2, 4, 5, 1, 3)$, $(2, 4, 5, 3, 1)$.