Calculate number of ways to write all $$$n!$$$ permutations in one line so that every two adjacent elements in line are different.

I am really stuck without any ideas. I even can't calculate for $$$n = 3$$$.

Of course it can be reformulated to smth like: we have $$$k$$$(in particular $$$(n-2)!$$$) pairs $$$(i, j): i\neq j$$$, calculate number of ways to write it in one line so that every two adjacent elements in line are different.

I would be very pleased to find out something faster than $$$O(2^{n!})$$$