24693번 - Implemented Incorrectly 다국어

문제

Consider the following problem:

• You are given a permutation $A = \langle a_1, a_2, \ldots, a_n \rangle$ containing each integer from 1ドル$ to $n$ exactly once. Find its only cyclic shift that starts with 1ドル$.

Consider the following algorithm to solve it:

• Input: $A = \langle a_1, a_2, \ldots, a_n \rangle$.
• For each $i = 2, 3, \ldots, n$:
  • if $a_i < a_1$:
    • rotate $A$ to move $a_i$ to the front; that is, set $A \leftarrow \langle a_i, a_{i+1}, \ldots, a_n, a_1, a_2, \ldots, a_{i-1} \rangle$.
• Output: $A = \langle a_1, a_2, \ldots, a_n \rangle$.

You are given a single integer $n$. Find the number of permutations on which the described algorithm solves the problem incorrectly.

입력

The only line contains a single integer $n$ (1ドル \le n \le 42$).

출력

Print the number of permutations on which the described algorithm works incorrectly.

제한

힌트

In the first example test case, for $n = 3,ドル the only permutation resulting in an incorrect output is $\langle 3, 2, 1 \rangle$. The algorithm returns $\langle 2, 1, 3 \rangle,ドル while the correct answer is $\langle 1, 3, 2 \rangle$.