컵🥛 timer 1s memory 128MB

N개의 컵에 N개의 서로 다른 음료를 담았다. 그러고는 아래와 같은 규칙에 따라 음료를 섞기로 했다.

1. 1~N의 번호가 메겨진 컵을 오름차순으로 일렬로 배치한다.

2. 어떤 두 컵을 골라 위치를 맞바꾼다. 이 작업을 \frac{N}2번 반복한다.

3. 모든 컵은 정확히 한 번씩 위치가 바뀌어야 한다. 자기 자신과는 위치를 바꿀 수 없다.

컵이 배열되는 경우의 수가 몇 가지인지 알아보자.