잘못 구현된 알고리즘

다음 문제를 생각해 보자.

• $1$부터 $n$까지의 정수가 각각 정확히 한 번씩 나타나는 순열 $A = \langle a_1, a_2, \ldots, a_n \rangle$이 주어진다. 이 순열의 순환 이동 중 $1$로 시작하는 것은 하나뿐이며, 그 순환 이동을 구하라.

이 문제를 다음 알고리즘으로 풀려고 한다.

• 입력: $A = \langle a_1, a_2, \ldots, a_n \rangle$
• $i = 2, 3, \ldots, n$에 대해 다음을 반복한다.
  • $a_i < a_1$이면, $A$를 회전시켜 $a_i$를 맨 앞으로 옮긴다. 즉 $A \leftarrow \langle a_i, a_{i+1}, \ldots, a_n, a_1, a_2, \ldots, a_{i-1} \rangle$로 둔다.
• 출력: $A = \langle a_1, a_2, \ldots, a_n \rangle$

이 알고리즘이 잘못 동작하는 순열의 개수를 구하라.

한 줄에 정수 $n$ ($1 \le n \le 42$)이 주어진다.

알고리즘이 잘못 동작하는 순열의 개수를 출력한다.

$n = 3$인 경우, 알고리즘이 틀리게 답하는 순열은 $\langle 3, 2, 1 \rangle$뿐이다. 알고리즘은 $\langle 2, 1, 3 \rangle$을 출력하지만, 올바른 답은 $\langle 1, 3, 2 \rangle$이다.