$1$ 到 $k$，每个数最多取 $2$ 遍，求长度为 $n$ 的排列数（$n\le 10^3,k\le 10^9$）。

求大佬解题思路，要求时间复杂度小于 $O(n^2)$。