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$.