GATE CSE 2023 Q48: Permutations of U that separate set A from set B

Let $U = \{1, 2, \ldots, n\}$, where $n$ is a large positive integer greater than 1000. Let $k$ be a positive integer less than $n$. Let $A, B$ be subsets of $U$ with $|A| = |B| = k$ and $A \cap B = \emptyset$. We say that a permutation of $U$ separates $A$ from $B$ if one of the following is true.

• All members of $A$ appear in the permutation before any of the members of $B$.

• All members of $B$ appear in the permutation before any of the members of $A$.

How many permutations of $U$ separate $A$ from $B$?